Subcoloring: Difference between revisions
m image replaced against svg version |
clarify relation to coloring |
||
| Line 6: | Line 6: | ||
Subcoloring and [[subchromatic number]] were introduced by Albertson et al. (1989). |
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 (mathematics)|set]] is also a disjoint union of induced cliques, namely ''K''<sub>1</sub>, subcoloring is also essentially a relaxed form of the traditional [[Graph coloring|vertex coloring]]. |
It follows from its definition immediately that subcoloring is a restricted form of [[cocoloring]]. Since an independent [[Set (mathematics)|set]] is also a disjoint union of induced cliques, namely ''K''<sub>1</sub>, subcoloring is also essentially a relaxed form of the traditional [[Graph coloring|vertex coloring]], and the subchromatic number of any graph is at most its [[chromatic number]]. However, such relaxation does not make this type of coloring "easier" than the traditional one. |
||
However, such relaxation does not make this type of [[color|coloring]] "easier" than the traditional one. |
|||
The problem of determining whether a [[triangle-free graph|triangle-free]] [[planar graph]] with maximum [[degree (graph theory)|degree]] 4 has [[subchromatic number]] at most 2 is [[NP-complete|'''NP'''-complete]] (Gimbel, Hartman 2003). |
The problem of determining whether a [[triangle-free graph|triangle-free]] [[planar graph]] with maximum [[degree (graph theory)|degree]] 4 has [[subchromatic number]] at most 2 is [[NP-complete|'''NP'''-complete]] (Gimbel, Hartman 2003). |
||
Revision as of 23:46, 17 April 2010
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).
It follows from its definition immediately that subcoloring is a restricted form 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, and the subchromatic number of any graph is at most its chromatic number. 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).
See also
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.