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 part. A graph is strongly k-colorable if, for each partition of the vertices into sets of size k, it admits a strong coloring. 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. 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): 1. * sχ(G) > Δ(G). 2. * sχ(G) ≤ 3 Δ(G) − 1. 3. * Asymptotically, sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). Here, Δ(G) is the maximum degree. Strong chromatic number was independently introduced by Alon (1988) and Fellows (1990). (Wikipedia).
