# Coloring the union of degenerate graphs

 Importance: Medium ✭✭
 Author(s): Tarsi, Michael
 Subject: Graph Theory » Coloring
 Keywords:
 Posted by: fhavet on: March 3rd, 2013
Conjecture   The union of a -degenerate graph (a forest) and a -degenerate graph is -colourable.

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

Conjecture   Every -composed graph is -colourable.

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.