A new polynomial on compositions of integers: on distinguishing caterpillars from their symmetric chromatic function

arXiv1208.0816MaRDI QIDQ6234832FDOQ6234832

Authors: José Aliste-Prieto, José Zamora 

Publication date: 3 August 2012

Abstract: In this paper, we propose an algebraic approach to determine whether two non-isomorphic caterpillar trees can have the same symmetric function generalization of the chromatic polynomial. On the set of all composition on integers, we introduce: An operation, which we call composition product; and a combinatorial polynomial, which we call the composition-lattice polynomial or L-polynomial, that mimics the weighted graph polynomial of Noble and Welsh. We prove a unique irreducible factorization theorem and establish a connection between the L-polynomial of a composition and its irreducible factorization, namely that reversing irreducible factors does not change L, and conjecture that is the only way of generating such compositions. Finally, we find a sufficient condition for two caterpillars have a different symmetric function generalization of the chromatic polynomial, and use this condition to show that if our conjecture were to hold, then the symmetric function generalization of the chromatic polynomial distinguishes among a large class of caterpillars.

This page was built for publication: A new polynomial on compositions of integers: on distinguishing caterpillars from their symmetric chromatic function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6234832)