- Series
- Graph Theory Seminar
- Time
- Thursday, February 10, 2011 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Chun-Hung Liu – Math, GT
- Organizer
- Robin Thomas
A graph is k-critical if it is not (k-1)-colorable but every proper subgraph is. In 1963, Gallai conjectured that every k-critical graph G of order n has at least (k-1)n/2 + (k-3)(n-k)/(2k-2) edges. The currently best known results were given by Krivelevich for k=4 and 5, and by Kostochka and Stiebitz for k>5. When k=4, Krivelevich's bound is 11n/7, and the bound in Gallai's conjecture is 5n/3 -2/3. Recently, Farzad and Molloy proved Gallai's conjecture for k=4 under the extra condition that the subgraph induced by veritces of degree three is connected. We will review the proof given by Krivelevich, and the proof given by Farzad and Molloy in the seminar.