Premium
A Relaxed Version of the Erdős–Lovász Tihany Conjecture
Author(s) -
Stiebitz Michael
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22060
Subject(s) - combinatorics , conjecture , mathematics , disjoint sets , vertex (graph theory) , fractional coloring , clique number , graph , chromatic scale , discrete mathematics , list coloring , clique , graph power , line graph
The Erdős–Lovász Tihany conjecture asserts that every graph G with ω ( G ) < χ ( G ) = s + t − 1( s , t ≥ 2 ) contains two vertex disjoint subgraphs G 1 and G 2 such that χ ( G 1 ) ≥ s and χ ( G 2 ) ≥ t . 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) χ ( G 1 ) ≥ s andcol ( G 2 ) ≥ t or (b)col ( G 1 ) ≥ s and χ ( G 2 ) ≥ t . Here, χ ( G ) is the chromatic number of G , ω ( G ) is the clique number of G , and col( G ) is the coloring number of G .