Groupe d’études et de recherche en analyse des décisions

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

## Alain Hertz, Hadrien Mélot, Sébastien Bonte et Gauvain Devillez

We study the average number $$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 $$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.

, 18 pages