Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

 

What makes the chromatic number of a graph large? There have been many attempts to answer this question. The most natural approach is to look for unavoidable substructures in graphs of large chromatic number. Hadwiger made the conjecture that every graph of chromatic number r can be transformed into a complete graph of r vertices by a series of edge contractions and vertex and edge deletions. This is known to be true for r<6. There are several related problems on embeddability properties of graphs that I plan to explain.          The crossing number of a graph G is the smallest number of edge crossings in a proper drawing of G in the plane. According to Albertson's conjecture, the crossing number of every graph of chromatic number r is at least as large as the chromatic number of a complete graph with r vertices. We settle Albertson's conjecture for graphs whose number of vertices is not much larger than their chromatic number. Joint work with Jacob Fox and Andrew Suk.