Arts & Sciences Events
[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Martin Rolek (William & Mary)
Access & Features
- Open to the public
Speaker: Martin Rolek (William & Mary)
Title: Partial results related to Hadwiger's conjecture and the double-critical graph conjecture
Abstract: A graph H is a minor of a graph G if H can be obtained from G by contracting edges. Hadwiger's conjecture from 1943 states that any graph which does not contain a complete minor on t vertices is (t-1)-colorable. This conjecture has been proved for t at most 6, but remains open for larger t. We prove a partial result by showing that any graph with no complete minor on t vertices is (2t - 6)-colorable for t = 7,8,9, in the process giving a shorter and computer-free proof of the known results for t = 7,8. We also prove that the same result extends to all values of t if a reasonable conjecture is assumed to be true.
A connected graph G is double-critical if for every edge xy of G, the chromatic number of G-x-y is 2 less than the chromatic number of G. The double-critical graph conjecture of Erd?s and Lov?sz from 1968 states that for all t, the only double-critical t-chromatic graph is the complete graph on t vertices. This conjecture is true for t at most 5, and remains open for larger t. We investigate the class of claw-free graphs and show that the conjecture holds for claw-free graphs if t is at most 8.