Strengthening Hadwiger's Conjecture
Fred C. Holroyd · Bulletin of the London Mathematical Society · 1997
We consider the following strengthening of Hadwiger's Conjecture. Let G be any graph of chromatic number k, S any subset of V(G) which takes all k colours in each proper k-colouring of G. Then there are k pairwise adjacent connected subgraphs of G, each of whose vertex sets has non-trivial intersection with S. We show that the truth of this conjecture for all graphs of chromatic number ⩽k implies the truth of Hadwiger's Conjecture for all graphs of chromatic number ⩽k + 1. We also show that its truth implies the following statement (which is at first sight even stronger). For any graph G of chromatic number k and any subset S of V(G), define χ(S; G) to be the least number of colours that can appear on S in any proper k-colouring of G, and h(S; G) to be the largest number of pairwise adjacent connected subgraphs of G each having non-trivial intersection with S. Then χ(S; G) ⩽ h(S; G). We define the number w(S; G) to be the largest cardinality of a subset T of S such that, however T is partitioned into pairs (possibly with one spare element), there are vertex-disjoint paths linking the elements in each pair, none passing through the spare element if it exists. We show that χ(S; G) ⩽ (|S| + w(S; G))/2 for any graph G and subset S of V(G). Finally, we show that for any graph G, χ(S; G) ⩽ h(S; G) whenever χ(S; G) ⩽ 3. 1991 Mathematics Subject Classification 05C15.