- Source: 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):
sχ(G) > Δ(G).
sχ(G) ≤ 3 Δ(G) − 1.
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).
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, 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
Kata Kunci Pencarian:
8.5
6.774
No More Posts Available.
No more pages to load.
