![](/files/happy5.png)
![$ 1 $](/files/tex/f81bea742c6e484717a25f7b16835462361c1d2e.png)
![$ 2 $](/files/tex/5271e36bb1c040e0f14061d89cd97d0c86d4e06f.png)
![$ 5 $](/files/tex/87f5fe1d4b06035debb52cf2d67802fbfa9cb4ab.png)
A graph is -degenerate if it can be reduced to
(the graph with a unique vertex) by repeatedly deleting vertices of degree at most
. A
-degenerate graph
admits a proper
-colouring
, and a
-degenerate graph
admits a proper
-colouring
. Thus,
is a proper
-colouring of
and
.
The conjecture is tigth because is the union of a
-degenerate graph and a
-degenerate graph.
Based on a decompostion of the complete graph, Klein and Schönheim [KlSc93] generalised this conjecture to -composed graphs, which are unions of
graphs
such that
is
-degenerate,
.
![$ (m_1, \dots, m_s) $](/files/tex/5b45b35258d6f538aabc3ac0969bc92d91f862be.png)
![$ \left(\sum_{i=1}^s m_i+\bigg\lfloor\frac{1}{2}\bigg(1+\sqrt{1+8\sum_{1\leq i<j\leq s}m_i m_j}\bigg)\bigg\rfloor\right) $](/files/tex/b0f514d9a9925fad1c74957e6e1df9b3a560a3e3.png)
Partial results towards this conjecture are obtained in [KlSc95].
Bibliography
*[K] R. Klein. On the colorability of {}-composed graphs. Discrete Math. 133 (1994), 181--190.
[KlSc93] R. Klein and J. Schönheim. Decomposition of {} into degenerate graphs. In Combinatorics and graph theory (Hefei, 1992), pages 141--155. World Sci. Publ., River Edge, NJ, 1993.
[KlSc95] R. Klein and J. Schönheim. On the colorability of graphs decomposable into degenerate graphs with specified degeneracy. Australas. J. Combin., 12:201--208, 1995.
* indicates original appearance(s) of problem.