Search

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. [ABSTRACT FROM AUTHOR]