Subcoloring

From Wikipedia, the free encyclopedia

In graph theory, a subcoloring is an assignment of colors to a graph's vertex 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). It follows from its definition immediately that it is a kind of cocoloring. Since an independent set is also a disjoint union of induced cliques, namely K₁, subcoloring is also essentially a relaxed form of the traditional vertex coloring. However, such relaxation does not make this type of coloring "easier" than the traditional one. The problem of determining whether a triangle-free planar graph with maximum degree 4 has subchromatic number at most 2 is NP-complete (Gimbel, Hartman 2003).

[edit] See also

• Cocoloring

[edit] References

• Albertson, M. O.; Jamison, R. E.; Hedetniemi, S. T.; Locke, S. C. (1989). The subchromatic number of a graph. Discrete Math. 74(1-2), 33–49.

• Gimbel, John; Hartman, Chris (2003). Subcolorings and the subchromatic number of a graph. Discrete Math. 272(2-3), 139–154.