BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UNIFR/WEBMASTER//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VTIMEZONE
TZID:Europe/Zurich
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
DTSTART:19810329T020000
TZNAME:CEST
TZOFFSETTO:+0200
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
DTSTART:19961027T030000
TZNAME:CET
TZOFFSETTO:+0100
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Zurich:20221102T140000Z
DTEND;TZID=Europe/Zurich:20221102T140000Z
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:Kolloquium / Kongress / Forum
LOCATION:PER 21\, B207\, Bd de Pérolles 90\, 1700 Fribourg
URL;VALUE=URI:https://agenda.unifr.ch/e/de/11911
END:VEVENT
END:VCALENDAR