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

Ken-Ichi Kawarabayashi (The National Institute of Informatics, Tokyo, Japan)

Anders Sune Pedersen (Department of Mathematics and Computer Science, University of Southern Denmark)

Bjarne Toft (Department of Mathematics and Computer Science, University of Southern Denmark)

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

Full Text (PDF format)