Contents Online

# Journal of Combinatorics

## Volume 2 (2011)

### Number 4

### The Erdös-Lovász Tihany conjecture and complete minors

Pages: 575 – 592

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n4.a6

#### Authors

#### Abstract

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$.

#### Keywords

graph colouring, graph decompositions, complete minors