Decomposing graphs into subgraphs with higher total chromatic number
Search
Subjects
- 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 Erdös
About This Site
Problem (proposed by Erdős and Lovász [6])
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 [6] is for the case \( k=5, a=b=3\), which was proved affirmatively by Brown and Jung [1]. Several small cases have been settled (for more discussion, see [3]). Recently (2008), Kostochka and Stiebitz [5] 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 [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 [4].