Strong coloring

This Möbius ladder is strongly 4-colorable. There are 35 4-sized partitions, but only these 7 partitions are topologically distinct.

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):

  1. sχ(G) > Δ(G).
  2. sχ(G) ≤ 3 Δ(G) − 1 (Haxell)
  3. 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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.