- Strong coloring
[
Thiscubic graph is strongly 4-colorable. The 4-sized partitions are 35, but only this 7 partitions are topologically unique.]In
graph theory , a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring in which every color appears exactly once in every partition.When the order of the graph "G" is not divisible by "k", we add isolated vertices to "G" just enough to make the order of the new graph "G′" divisible by "k".In that case, a strong coloring of "G′" minus the previously added isolated vertices is considered a strong coloring of "G".A graph is strongly "k"-colorable if, for each partition of the vertices into sets of size "k", it admits a strong coloring.The strong chromatic number sχ("G") of a graph "G" is the least "k" such that "G" is strongly "k"-colorable.A graph is strongly "k"-chromatic if it has strong chromatic number "k".
Some properties of sχ("G"):
# sχ("G") > Δ("G").
# sχ("G") ≤ 3 Δ("G") − 1 (Haxell)
# Asymptotically, sχ("G") ≤ 11 Δ("G") / 4 + o(Δ("G")). (Haxell)Here Δ("G") is the maximum degree.Strong chromatic number was independently introduced by Alon (1988) and Fellows (1990).
References
* Alon, Noga (1988). The linear arboricity of a graph. "Israel J. Math." 62, 311–325.
* Alon, Noga (1992). The strong chromatic number. "Random Structures and Algorithms" 3, 1–7.
* Fellows, Michael R. (1990). Transversals of vertex partition in graphs. "SIAM J. Discrete Math." 3, 206–215.
* Jensen, Tommy R.; Toft, Bjarne (1995). "Graph coloring problems". New York: Wiley-Interscience. ISBN 0-471-02865-7.
Wikimedia Foundation. 2010.
