Strong coloring
|
|
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) ≤ c Δ(G) for some large constant c. (Alon 1992)
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.