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

Abstract

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.

Keywords:

• Primary 05C15
• Chromatic polynomial
• log-concavity
• subgraphs