Georgia Institute of Technology College of Sciences

The Four Color Theorem states that every planar graph is 4-colorable. Hajos conjectured that for any positive integer k, every graph containing no K_{k+1}-subdivision is k-colorable. However, Catlin disproved Hajos' conjecture for k >= 6. It is not hard to prove that the conjecture is true for k <= 3. Hajos' conjecture remains open for k = 4 and k = 5. We consider a minimal counterexample to Hajos' conjecture for k = 4: a graph G, such that G contains no K_5-subdivision, G is not 4-colorable, and |V (G)| is minimum. We use Hajos graph to denote such counterexample. One important step to understand graphs containing K_5-subdivisions is to solve the following problem: let H represent the tree on six vertices, two of which are adjacent and of degree 3. Let G be a graph and u1, u2, a1, a2, a3, a4 be distinct vertices of G. When does G contain a topological H (i.e. an H-subdivision) in which u1, u2 are of degree 3 and a1, a2, a3, a4 are of degree 1? We characterize graphs with no topological H. This characterization is used by He, Wang, and Yu to show that graph containing no K_5-subdivision is planar or has a 4-cut, establishing conjecture of Kelmans and Seymour. Besides the topological H problem, we also obtained some further structural information of Hajos graphs.