Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials

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...

Full description

Saved in:
Bibliographic Details
Published in:Experimental mathematics 2006-01, Vol.15 (3), p.343-353
Main Authors: Lundow, P. H., Markström, K.
Format: Article
Language:English
Subjects:
05C15
bounds
Chromatic polynomial
log-concavity
Primary 05C15
subgraphs
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ε(G), the average size of a broken-cyclefree subgraph of the graph G, whose behavior under edge deletion and contraction is studied.
ISSN:1058-6458
1944-950X
1944-950X
DOI:10.1080/10586458.2006.10128969