Lower Bounds and properties for the average number of colors in the non-equivalent colorings of a graph

Abstract

We study the average number $\mathcal{A}(G)$ of colors in the non-equivalent colorings of a graph $G$. We show some general properties of this graph invariant and determine its value for some classes of graphs. We then conjecture several lower bounds on $\mathcal{A}(G)$ and prove that these conjectures are true for specific classes of graphs such as triangulated graphs and graphs with maximum degree at most 2.

20 pages, 2 figures

References in corpus (1)

• Using Graph Theory to Derive Inequalities for the Bell Numbers

Cited by in corpus (1)

• Upper bounds on the average number of colors in the non-equivalent colorings of a graph