BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UNIFR/WEBMASTER//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTSTART;VALUE=DATE:20221102T160000
DTEND;VALUE=DATE:20221102T160000
UID:11911@agenda.unifr.ch
DESCRIPTION: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).\nWe 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.\n
SUMMARY:On the average number of colors in the non-equivalent colorings of a graph
CATEGORIES:Colloque / Congrès / Forum
LOCATION:PER 21\, B207\, Bd de Pérolles 90\, 1700 Fribourg
URL;VALUE=URI:https://agenda.unifr.ch/e/fr/11911
END:VEVENT
END:VCALENDAR