A Relaxed Version of the Erdős–Lovász Tihany Conjecture |
| |
| Authors: | Michael Stiebitz |
| |
| Affiliation: | INSTITUTE OF MATHEMATICS, TECHNISCHE UNIVERSIT?T ILMENAU, ILMENAU, GERMANY |
| |
| Abstract: | The Erd?s–Lovász Tihany conjecture asserts that every graph G with   ) contains two vertex disjoint subgraphs G 1 and G 2 such that  and  . Under the same assumption on G , we show that there are two vertex disjoint subgraphs G 1 and G 2 of G such that (a)  and  or (b)  and  . Here,  is the chromatic number of  is the clique number of G , and col(G ) is the coloring number of G . |
| |
| Keywords: | coloring decomposition double‐critical graphs |
|
|
