Reducing Hajos' 4-coloring conjecture to 4-connected graphs

Hajos conjectured that, for any positive. integer k, every graph containing no Kk+1-subdivision is k-colorable. This is true when k <= 3, and false when k >= 6. Hajos' conjecture remains open for k=4,5. In this paper, we show that any possible counterexample to this conjecture for k=4 with minimum number of vertices must be 4-connected. This is a step in an attempt to reduce Hajos' conjecture for k=4 to the conjecture of Seymour that any 5-connected non-planar graph contains a K-5-subdivision. (C) 2005 Elsevier Inc. All rights reserved.