Colloquium talk: Improved Bounds on the List Colouring Conjecture
- Date
- November 28, 2024
- Time
- 12:10 PM EST - 1:00 PM EST
- Location
- KHE321B
- Open To
- All faculty, staff, students, and guests are welcome to attend
- Contact
- pralat@torontomu.ca
TORONTO METROPOLITAN UNIVERSITY
DEPARTMENT OF MATHEMATICS
COLLOQUIUM
Dr. Michael Molloy
Department of Computer Science
University of Toronto
Date: Thursday, November 28, 2024
Time: 12:10 pm
Location: KHE321B
Improved Bounds on the List Colouring Conjecture
Abstract:
Suppose you have a graph with a list of colours on every vertex. You wish to properly colour the graph so that every vertex gets a colour from its list. This is a widely studied variation of graph colouring and, in many applications, is a more accurate model of real world constraints.
The List Colouring Conjecture concerns colouring the edges of a graph in this manner. It posits (roughly speaking) that if each edge is assigned a list of D + 1 colours then it is always possible to obtain a proper edge colouring by choosing one colour from each list.
In the 1990’s, Kahn proved that one can always obtain a proper edge colouring from lists of size D + o(D), then Molloy and Reed obtained D + D1/2poly(log D). We improve that bound to D + D2/5poly(log D).
All Faculty, staff, students and guests are welcome to attend
