On the average number of colors in the non-equivalent colorings of a graph

Colloque / Congrès / Forum
Ouvert au grand public
02.11.2022 16:00

A coloring of a graph G is an assignment of colors to its vertices such that adjacent vertices have different colors. Two colorings of a graph are equivalent if they induce the same partition of the vertex set into stable sets (i.e., sets of pairwise non-adjacent vertices). The n-th Bell number is the number of partitions of a set of n elements into non-empty subsets and is thus the same as the number of non-equivalent colorings of the empty graph or order n (i.e., the graph with n vertices and without any edge).
We are interested in the average number A(G) of colors in the non-equivalent colorings of a graph G. We give properties of this new graph invariant and show how it can help derive inequalities for the Bell numbers. We then prove some bounds on A(G). In particular, we give a general upper bound on A(G) that is valid for all graphs G and a more precise one for graphs G of order n and maximum degree in {1, 2, n − 2}. 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. We finish with many open questions.
02.11.2022 16:00
Site PER 21 / Salle B207
Bd de Pérolles 90, 1700 Fribourg
Département d'Informatique
Stéphanie Fasel
Bd de Pérolles 90
1700 Fribourg
Prof. Alain Hertz, Polytechnique Montréal & GERAD, Canada
Pièces jointes