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:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69cf6bacec6de
DTSTART;TZID=America/Toronto:20241126T140000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20241126T150000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/graphs-and-m
 atroids-cynthia
SUMMARY:Graphs and Matroids - Cynthia
CLASS:PUBLIC
DESCRIPTION:TITLE: On the relation among $\\Delta$\, $\\chi$ and $\\omega$\
 n\nSPEAKER:\n Cynthia\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION
 :\n MC 5417\n\nABSTRACT:I will present some work from my MMath thesis\, wh
 ich is on\nthe relation among the maximum degree $\\Delta(G)$\, the chroma
 tic\nnumber $\\chi(G)$ and the clique number $\\omega(G)$ of a graph $G$. 
 In\nparticular\, we focus on two important and long-standing conjectures o
 n\nthis subject\, the Borodin-Kostochka Conjecture and Reed's Conjecture.\
 nIn 1977\, Borodin and Kostochka conjectured that given a graph $G$ with\n
 $\\Delta(G) \\ge 9$\, if $\\chi(G) = \\Delta(G)$\, then $\\omega(G) =\n\\D
 elta(G)$. This is a step toward strengthening the well-known Brooks'\nTheo
 rem. In 1998\, Reed proposed a more general conjecture\, which\nstates tha
 t $\\chi(G) \\le \\lceil \\frac{1}{2} (\\Delta(G)+\\omega(G)+1)\n\\rceil$ 
 for any graph $G$.\n\nIn this talk\, we show a weaker but more general Bor
 odin-Kostochka-type\nresult. That is\, given a nonnegative integer $t$\, f
 or every graph $G$\nwith $\\Delta(G) \\ge 4t^2+11t+7$ and $\\chi(G) = \\De
 lta(G)-t$\, the graph\n$G$ contains a clique of size $\\Delta(G)-2t^2-7t-4
 $. We introduce the\ntechnique of Mozhan partitions and give a high-level 
 overview of the\nproof. This generalizes some previous work on this topic.
  Then\, we\nprove that both conjectures hold for odd-hole-free graphs. Las
 tly\, we\ndiscuss a few constructions of classes of graphs for which Reed'
 s\nConjecture holds with equality\, including a new family of irregular\nt
 ight examples.\n\n 
DTSTAMP:20260403T072636Z
END:VEVENT
END:VCALENDAR