W&M Homepage

Location

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.

This Event Appears On

• W&M Featured Events
• Arts & Sciences Events
• Mathematics Events