BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20260308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20251102T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:6adbad8b17062
DTSTART;TZID=America/Toronto:20261026T150000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20261026T160000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/graphs-and-m
 atroids-hidde-koerts-faster-3-colouring
SUMMARY:Graphs and Matroids | Hidde Koerts\, Faster 3-colouring algorithm f
 or\ngraphs of diameter 3
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n Hidde Koerts \n\nAFFILIATION:\n University of Water
 loo\n\nROOM:\n MC 6029\n\nABSTRACT: Determining whether a graph is k-colo
 urable is a famously\nhard computational problem. Even when placing signif
 icant restrictions\non the graph\, the resulting problem is often NP-hard.
  In this talk\,\nwe focus on the case of restricting the diameter. Under 
 the\nExponential Time Hypothesis\, there does not exist a sub-exponential\
 nalgorithm for 3-colouring diameter-4 graphs or for 4-colouring\ndiameter-
 2 graphs. Hence\, the interesting remaining cases are\n3-colouring graphs 
 of diameter 2 or 3. We show that 3-colouring\ndiameter-3 graphs can be so
 lved in 2^O(n^{2/3−ε}) for any ε < 1/33\nby providing an algorithm bas
 ed on a structural result. This improves\non the previous best known algor
 ithm due to Dębski\, Piecyk and\nRzążewski.\n\nThis talk is based on jo
 int work with Carla Groenland and Sophie\nSpirkl.
DTSTAMP:20261023T185507Z
END:VEVENT
END:VCALENDAR