{{short description|(proper) vertex coloring}} [[Image:Strong coloring sample.svg|400px|right|thumb| 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 ''{{prime|G}}'' divisible by ''k''. In that case, a strong coloring of ''{{prime|G}}'' minus the previously added isolated vertices is considered a strong coloring of ''G''. <ref>{{Cite book|last=Jensen, Tommy R.|title=Graph coloring problems|date=1995|publisher=Wiley|others=Toft, Bjarne.|isbn=0-471-02865-7|location=New York|oclc=30353850}}</ref>
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.<ref>{{Cite journal|last=Haxell|first=P. E.|date=2004-11-01|title=On the Strong Chromatic Number|url=http://www.journals.cambridge.org/abstract_S0963548304006157|journal=Combinatorics, Probability and Computing|language=en|volume=13|issue=6|pages=857–865|doi=10.1017/S0963548304006157|s2cid=6387358 |issn=0963-5483|url-access=subscription}}</ref> # Asymptotically, sχ(''G'') ≤ 11 Δ(''G'') / 4 + o(Δ(''G'')).<ref>{{Cite journal|last=Haxell|first=P. E.|date=2008|title=An improved bound for the strong chromatic number|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.20300|journal=Journal of Graph Theory|language=en|volume=58|issue=2|pages=148–158|doi=10.1002/jgt.20300|s2cid=20457776 |issn=1097-0118|url-access=subscription}}</ref> Here, Δ(''G'') is the maximum degree.
Strong chromatic number was independently introduced by Alon (1988)<ref>{{Cite journal|last=Alon|first=N.|author-link=Noga Alon|date=1988-10-01|title=The linear arboricity of graphs|journal=Israel Journal of Mathematics|language=en|volume=62|issue=3|pages=311–325|doi=10.1007/BF02783300|doi-access=free|issn=0021-2172}}</ref><ref>{{Cite journal|last=Alon|first=Noga|date=1992|title=The strong chromatic number of a graph|url=http://doi.wiley.com/10.1002/rsa.3240030102|journal=Random Structures & Algorithms|language=en|volume=3|issue=1|pages=1–7|doi=10.1002/rsa.3240030102}}</ref> and Fellows (1990).<ref>{{Cite journal|last=Fellows|first=Michael R.|date=1990-05-01|title=Transversals of Vertex Partitions in Graphs|url=http://epubs.siam.org/doi/10.1137/0403018|journal=SIAM Journal on Discrete Mathematics|language=en|volume=3|issue=2|pages=206–215|doi=10.1137/0403018|issn=0895-4801|url-access=subscription}}</ref>
== 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'''.<ref name=":2">{{Cite journal|last=Haxell|first=P.|date=2011-11-01|title=On Forming Committees|url=https://www.tandfonline.com/doi/abs/10.4169/amer.math.monthly.118.09.777|journal=The American Mathematical Monthly|volume=118|issue=9|pages=777–788|doi=10.4169/amer.math.monthly.118.09.777|s2cid=27202372 |issn=0002-9890|url-access=subscription}}</ref>
== References == {{Reflist}} Category:Graph coloring