Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials
Lundow, P. H. ; Markström, K.
Experiment. Math., Tome 15 (2006) no. 1, p. 343-354 / Harvested from Project Euclid
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 $\varepsilon(G)$, the average size of a broken-cycle-free subgraph of the graph $G$, whose behavior under edge deletion and contraction is studied.
Publié le : 2006-05-14
Classification:  Chromatic polynomial,  log-concavity,  subgraphs,  05C15
@article{1175789763,
     author = {Lundow, P. H. and Markstr\"om, K.},
     title = {Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials},
     journal = {Experiment. Math.},
     volume = {15},
     number = {1},
     year = {2006},
     pages = { 343-354},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1175789763}
}
Lundow, P. H.; Markström, K. Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials. Experiment. Math., Tome 15 (2006) no. 1, pp.  343-354. http://gdmltest.u-ga.fr/item/1175789763/