Agenda

02
Nov

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

General public Colloquium / Congress / Forum

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.


When? 02.11.2022 16:00
Where? PER 21 B207
Bd de Pérolles 90
1700 Fribourg
speaker Prof. Alain Hertz, Polytechnique Montréal & GERAD, Canada
Contact Département d'Informatique
Stéphanie Fasel
stephanie.fasel@unifr.ch
Bd de Pérolles 90
1700 Fribourg
0263008322
Attachment
backtolist