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