Decomposing graphs into subgraphs with higher total chromatic number

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].

Bibliography
1 W. G. Brown and H. A. Jung, On odd circuits in chromatic graphs, Acta Math. Acad. Sci. Hungar. 20 (1969), 129-134.

2 J. Balogh, A.V. Kostochka, N. Prince, and M. Stiebitz , The ErdősÐLov‡sz Tihany conjecture for quasi-line graphs, Disc. Math. 309 (2009), 3985-3991.

3 T. R. Jensen and B. Toft, Graph Coloring Problems, John Wiley and Sons, New York, 1995.

4 K. Kawarabayashi, A.S. Pederson and B. Toft Double-critical graphs and complete minors , The E. J. of Cobinatorics 17 (2010), 1.

5 A.V. Kostochka and M. Stiebitz , Partitions and Edge Colourings of Multigraphs, E. J. of Combinatorics 15 (2008), 1.

6 P. Erdős, Problem 2, Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 361, Academic Press, New York, 1968.