Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials
2006 (English)In: Experimental Mathematics, ISSN 1058-6458, E-ISSN 1944-950X, Vol. 15, no 3, 343-353 p.Article in journal (Refereed) Published
This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we give a number of conjectures and theorems regarding the behavior of the coefficients of the chromatic polynomial, in part motivated by our computations. Here our focus is on epsilon(G), the average size of a broken-cycle-free subgraph of the graph G, whose behavior under edge deletion and contraction is studied.
Place, publisher, year, edition, pages
2006. Vol. 15, no 3, 343-353 p.
chromatic polynomial, log-concavity, subgraphs, bounds
IdentifiersURN: urn:nbn:se:umu:diva-52130DOI: 10.1080/10586458.2006.10128969ISI: 000241619800006OAI: oai:DiVA.org:umu-52130DiVA: diva2:497212