Originator: Paul Seymour (presented by John Lenz - REGS 2008)
Definitions: A connected set in a graph is a set of vertices inducing a connected subgraph. Two disjoint vertex sets touch if some edge has an endpoint in both. A minor of a graph is a graph obtained from it by deleting and/or contracting some edges. A Kr-minor in a graph is a family of r disjoint pairwise touching connected sets; contracting these induced subgraphs and deleting irrelevant edges yields Kr as a minor. These connected sets are called branch sets, since they contract to the vertices of the minor.
Let α(G) denote the maximum size of an independent set of vertices in G. We restrict our attention to n-vertex graphs.
Background: Hadwiger's Conjecture states that every r-chromatic graph has a Kr-minor. Rather than attack the full generality of Hadwiger's Conjecture directly, we consider weaker statements. For example, since χ(G)≥n/α(G), Hadwiger's Conjecture implies Conjecture 1.
Conjecture 1: Every graph G has Kn/α(G) as a minor.
Comments: Duchet and Meyniel [DM] proved that G has Kn/(2α(G)-1) as a minor (see Toft [T]). For α(G)≥3, Kawarabayashi, Plummer, and Toft [KPT] improved this by guaranteeing a K2n/(4α(G)-3)-minor.
When α(G)=2, it is not hard to show that G has a Kn/3-minor. Let H1,…,Hk be a maximal set of disjoint induced 3-vertex induced paths in G. The remaining vertices of G form a union of disjoint cliques (since the induced subgraph has no induced 3-vertex path). Since α(G) = 2, there are at most two cliques in this set. Also, α(G) = 2 implies that the vertex sets of H1,…,Hk are pairwise touching. Hence G has a Kk+(n-3k)/2-minor. Since k≤n/3, there are at least n/3 branch sets. Seymour (unpublished) requested a proof that the constant 1/3 can be improved when α(G)=2.
Conjecture 2: There is a positive constant &epsilon such that every graph G with α(G)=2 has K(1/3+ε)n as a minor.
Definitions: A connected matching is a matching whose edges, viewed as vertex sets of size 2, form pairwise touching sets. This term is a misnomer, since no matching with more than one edge forms a connected graph.
Conjecture 3: There is a positive constant c such that every graph G with α(G)=2 contains a connected matching of size cn.
Comments: Thomassé was the first to notice that Conjectures 2 and 3 are equivalent; a proof appears in [KPT].
A connected matching yields a clique minor with a very restricted form; all branch sets have size 2. This led Seymour to another version of Conjecture 1 for graphs with independence number 2, called the SSH Conjecture by Blasiak.
Conjecture 4 (The SSH Conjecture): If α(G) = 2, then G has a Kn/2-minor in which all branch sets have size at most 2.
Comments: The best results in this direction were found by Blasiak [B], who proved that Conjecture 4 is true for graphs having an even number of vertices and either fractional clique covering number less than 3 or clique covering number 3. Blasiak [B] also showed that when n is sufficiently large, α(G)=2 guarantees the existence of a complete minor with at least n4/5/9 branch sets of size at most 2.
References:
[B] J. Blasiak. A special case of Hadwiger's conjecture. J. Combinatorial
Theory B, 97:1056-1073, 2007 doi:10.1016/j.physletb.2003.10.071
[DM] P. Duchet, H. Meyniel, On Hadwiger's number and the stability
number, Ann. Discrete Math. 13 (1982) 71-74.
[KPT] K. Kawarabayashi, M. Plummer, and B. Toft. Improvements of the
theorem of Duchet and Meyniel on Hadwiger's conjecture. J. Combinatorial
Theory B, 95:152-167, 2005 doi:10.1016/j.physletb.2003.10.071
[Toft] B. Toft. A basic elementary form of the Duchet-Meyniel Theorem.
2007 Preprint.