Strong coloring

From HandWiki
Revision as of 14:41, 6 February 2024 by MedAI (talk | contribs) (linkage)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Short description: (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. [1]

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.[2]
  3. Asymptotically, sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)).[3]

Here, Δ(G) is the maximum degree.

Strong chromatic number was independently introduced by Alon (1988)[4][5] and Fellows (1990).[6]

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.[7]

References

  1. Jensen, Tommy R. (1995). Graph coloring problems. Toft, Bjarne.. New York: Wiley. ISBN 0-471-02865-7. OCLC 30353850. https://www.worldcat.org/oclc/30353850. 
  2. Haxell, P. E. (2004-11-01). "On the Strong Chromatic Number" (in en). Combinatorics, Probability and Computing 13 (6): 857–865. doi:10.1017/S0963548304006157. ISSN 0963-5483. http://www.journals.cambridge.org/abstract_S0963548304006157. 
  3. Haxell, P. E. (2008). "An improved bound for the strong chromatic number" (in en). Journal of Graph Theory 58 (2): 148–158. doi:10.1002/jgt.20300. ISSN 1097-0118. https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.20300. 
  4. Alon, N. (1988-10-01). "The linear arboricity of graphs" (in en). 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" (in en). Random Structures & Algorithms 3 (1): 1–7. doi:10.1002/rsa.3240030102. http://doi.wiley.com/10.1002/rsa.3240030102. 
  6. Fellows, Michael R. (1990-05-01). "Transversals of Vertex Partitions in Graphs" (in en). SIAM Journal on Discrete Mathematics 3 (2): 206–215. doi:10.1137/0403018. ISSN 0895-4801. http://epubs.siam.org/doi/10.1137/0403018. 
  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. https://www.tandfonline.com/doi/abs/10.4169/amer.math.monthly.118.09.777.