Journal of Combinatorics
Volume 2 (2011)
The Erdös-Lovász Tihany conjecture and complete minors
Pages: 575 – 592
The Erdos-Lovász Tihany Conjecture [Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, 1968] states that for any pair of integers $s, t ≥ 2$ and for any graph $G$ with chromatic number equal to $s+t−1$ and clique number less than $s+t−1$ there are two disjoint subgraphs of $G$ with chromatic number $s$ and $t$, respectively. The Erdos-Lovász Tihany Conjecture is still open except for a few small values of $s$ and $t$. Given the same hypothesis as in the Erdos-Lovász Tihany Conjecture, we study the problem of finding two disjoint subgraphs of $G$ with complete minors of order $s$ and $t$, respectively. If Hadwiger’s Conjecture holds, then this latter problem might be easier to settle than the Erdos -Lovász Tihany Conjecture. In this paper we settle this latter problem for a few small additional values of $s$ and $t$.
graph colouring, graph decompositions, complete minors