Decomposing graphs into subgraphs with higher total chromatic number
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About This Site
Problem (proposed by Erdős and Lovász )Suppose a graph \(G\) has chromatic number \(k\) and contains no \(K_k\) as a subgraph. Let \(a\) and \(b\) denote two integers satisfying \(a,b \geq 2\) and \(a+b=k+1\). Do there exist two disjoint subgraphs of \(G\) with chromatic numbers \(a\) and \(b\), respectively?
The original question of Erdős  is for the case \( k=5, a=b=3\), which was proved affirmatively by Brown and Jung . Several small cases have been settled (for more discussion, see ). Recently (2008), Kostochka and Stiebitz  proved the conjecture for line graphs of multigraphs, and in (2009) with Balogh and Prince proved the conjecture for quasi-line graphs and graphs with independence number 2 .
Of special interest is the following case of \( a=2\):
Suppose the chromatic number of \( G\) decreases by \( 2\) whenever any two adjacent vertices are removed - such graphs are called double-critical. Must \( G\) be a complete graph?
Recently, Kawarabayashi, Pederson and Toft proved a relaxed version of the conjecture: namely, that any 6 or 7 chromatic double-critical graph can be contracted to a complete graph on 6 or 7 vertices, respectively .