Hadwiger’s Conjecture for Dense Strongly Regular Graphs

The famous Four-Color Conjecture (now Theorem) states that any planar graph could be colored using four colors. Hadwiger’s conjecture strengthens the Four-Color Conjecture by asserting that every graph with chromatic number t contains a complete minor of order t. In this paper we investigate Hadwiger’s conjecture for the complements of the Petersen graph and the Clebsch graph; both are strongly regular graphs with independence number two (hence dense graphs). We confirm Hajós’ conjecture, hence Hadwiger’s conjecture, for these graphs. Moreover, we show that for each of these graphs the exact hadwiger number is strictly greater its chromatic number.