Misplaced Pages

Strong coloring

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Strong chromatic number) (proper) vertex 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 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):

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

  1. Jensen, Tommy R. (1995). Graph coloring problems. Toft, Bjarne. New York: Wiley. ISBN 0-471-02865-7. OCLC 30353850.
  2. Haxell, P. E. (2004-11-01). "On the Strong Chromatic Number". Combinatorics, Probability and Computing. 13 (6): 857–865. doi:10.1017/S0963548304006157. ISSN 0963-5483. S2CID 6387358.
  3. Haxell, P. E. (2008). "An improved bound for the strong chromatic number". Journal of Graph Theory. 58 (2): 148–158. doi:10.1002/jgt.20300. ISSN 1097-0118. S2CID 20457776.
  4. Alon, N. (1988-10-01). "The linear arboricity of graphs". Israel Journal of Mathematics. 62 (3): 311–325. doi:10.1007/BF02783300. ISSN 0021-2172.
  5. Alon, Noga (1992). "The strong chromatic number of a graph". Random Structures & Algorithms. 3 (1): 1–7. doi:10.1002/rsa.3240030102.
  6. Fellows, Michael R. (1990-05-01). "Transversals of Vertex Partitions in Graphs". SIAM Journal on Discrete Mathematics. 3 (2): 206–215. doi:10.1137/0403018. ISSN 0895-4801.
  7. Haxell, P. (2011-11-01). "On Forming Committees". The American Mathematical Monthly. 118 (9): 777–788. doi:10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.
Category: