Subcoloring
|
|
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 K1, 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 planar, K3-free graphs with maximum degree 4 has subchromatic number at most 2 is NP-complete. (Gimbel, Hartman 2003)
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.