Strong coloring


In graph theory, a strong coloring, with respect to a partition of the vertices into subsets of equal sizes, is a 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χ 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χ:
  1. sχ > Δ.
  2. sχ ≤ 3 Δ − 1
  3. Asymptotically, sχ ≤ 11 Δ / 4 + o.
Here Δ is the maximum degree.
Strong chromatic number was independently introduced by Alon and Fellows.