In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...

 in which every color appears exactly once in every partition.
When the order

Glossary of graph theory

Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....

 of the graph G is not divisible by k, we add isolated vertices

Glossary of graph theory

Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....

 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

Glossary of graph theory

Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....

.

Strong chromatic number was independently introduced by Alon (1988) and Fellows (1990).