The Erdös-Lovász Tihany conjecture and complete minors
| Autor: | Bjarne Toft, Ken-ichi Kawarabayashi, Anders Sune Pedersen |
|---|---|
| Rok vydání: | 2011 |
| Předmět: | |
| Zdroj: | Toft, B, Pedersen, A S & Kawarabayashi, K 2012, ' The Erdös-Lovász Tihany Conjecture and complete minors ', Journal of Combinatorics, vol. 2, no. 4, pp. 575-592 . |
| ISSN: | 2150-959X 2156-3527 |
| DOI: | 10.4310/joc.2011.v2.n4.a6 |
| Popis: | The Erdős-Lovasz 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 Erdős-Lovasz Tihany Conjecture is still open except for a few small values of s and t. Given the same hypothesis as in the Erdős-Lovasz 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 Erdős-Lovasz Tihany Conjecture. In this paper we settle this latter problem for a few small additional values of s and t. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|