Titre : Number of non-equivalent colorings of a graph

Conférencier : MÉLOT, Hadrien (Université de Mons, Belgique)

Résumé:
What is the number of proper colorings of a given graph G or order n? Since more than a century, the common answer to the above question is related to the notion of chromatic polynomial introduced by Birkhoff in 1912. Let define Pi(G, k) as the number of ways of coloring G with at most k colors, counting two colorings as distinct when they are obtained by a permutation from the other. The chromatic polynomial is the polynomial of degree n passing by points (k, Pi(G, k)) for k = 0, 1,... , n. The number of vertex proper colorings of a graph G is nowadays commonly interpreted as Pi(G, n). We argue that the number of non-equivalent proper colorings with an exact number k of used colors is also of interest. This is especially the case when a set of elements has to be partitioned into a given number of k non-empty subsets, subject to some constraints.

In this talk, we start with a formal definition of the total number P(G) of non-equivalent vertex colorings of a graph G and we show similarities and differences between this invariant and the chromatic polynomial. Then, we address the problem of computing P(G), and we give exact values for some particular graphs. Finally, we prove some bounds on P(G) for graphs of bounded maximum degree and let other bounds as open problems.
(Joint work with Alain Hertz, GERAD)

Entrée libre

Bienvenus à tous.