In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, 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 ' divisible by ''k''. In that case, a strong coloring of ' 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''):
# sχ(''G'') > Δ(''G'').
# sχ(''G'') ≤ 3 Δ(''G'') − 1.
# Asymptotically, sχ(''G'') ≤ 11 Δ(''G'') / 4 + o(Δ(''G'')).
Here, Δ(''G'') is the
maximum degree
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
.
Strong chromatic number was independently introduced by Alon (1988) and Fellows (1990).
Related problems
Given a graph and a partition of the vertices, an
independent transversal is a set ''U'' of non-adjacent vertices such that each part contains exactly one vertex of ''U''. A strong coloring is equivalent to a partition of the vertices into disjoint independent-transversals (each independent-transversal is a single "color"). This is in contrast to
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 o ...
, which is a partition of the vertices of a graph into a given number of
independent sets, without the requirement that these independent sets be transversals.
To illustrate the difference between these concepts, consider a faculty with several departments, where the dean wants to construct a committee of faculty members. But some faculty members are in conflict and will not sit in the same committee. If the "conflict" relations are represented by the edges of a graph, then:
* An independent set is a committee with no conflict.
* An independent transversal is a committee with no conflict, with exactly one member from each department.
* A graph coloring is a partitioning of the faculty members into committees with no conflict.
* A strong coloring is a partitioning of the faculty members into committees with no conflict and with exactly one member from each department. Thus this problem is sometimes called the happy dean problem.
References
{{Reflist
Graph coloring