- Subcoloring
In
graph theory , a subcoloring is an assignment ofcolor s 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 ).It follows from its definition immediately that it is a kind ofcocoloring .Since an independent set is also a disjoint union of induced cliques, namely "K"1, 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-freeplanar graph with maximum degree 4 hassubchromatic number at most 2 is NP-complete (Gimbel, Hartman2003 ).See also
*
Cocoloring 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.
Wikimedia Foundation. 2010.
