Subcoloring

File:Subcoloring graph.svg

In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques.

A subchromatic number χ_S(G) of a graph G is the least number of colors needed in any subcoloring of G.

Subcoloring and subchromatic number were introduced by Albertson et al. (1989).

Every proper coloring and cocoloring of a graph are also subcolorings, so the subchromatic number of any graph is at most equal to the cochromatic number, which is at most equal to the chromatic number.

Subcoloring is as difficult to solve exactly as coloring, in the sense that (like coloring) it is NP-complete. More specifically, the problem of determining whether a graph has subchromatic number at most 2 is NP-complete, even for

• triangle-free planar graphs with maximum degree 4 (Gimbel & Hartman 2003) (Fiala et al. 2003),
• planar perfect graphs with maximum degree 4 (Gonçalves & Ochem 2009),
• planar graphs with girth 5 (Montassier & Ochem 2015).

References

• .
• .
• .
• .
• .