Strong coloring: Difference between revisions
m →References: Journal cites:, added 1 DOI, using AWB (7778) |
|||
Line 21: | Line 21: | ||
== References == |
== References == |
||
* {{cite journal | last1 = Alon | first1 = Noga | authorlink = Noga Alon | year = 1988 | title = The linear arboricity of a graph | url = | journal = Israel J. Math. | volume = 62 | issue = | pages = 311–325 }} |
* {{cite journal | last1 = Alon | first1 = Noga | authorlink = Noga Alon | year = 1988 | title = The linear arboricity of a graph | url = | journal = Israel J. Math. | volume = 62 | issue = | pages = 311–325 | doi=10.1007/BF02783300}} |
||
* {{cite journal | doi = 10.1002/rsa.3240030102 | last1 = Alon | first1 = Noga | authorlink = Noga Alon | year = 1992 | title = The strong chromatic number | url = | journal = Random Structures and Algorithms | volume = 3 | issue = | pages = 1–7 }} |
* {{cite journal | doi = 10.1002/rsa.3240030102 | last1 = Alon | first1 = Noga | authorlink = Noga Alon | year = 1992 | title = The strong chromatic number | url = | journal = Random Structures and Algorithms | volume = 3 | issue = | pages = 1–7 }} |
||
* {{cite journal | doi = 10.1137/0403018 | last1 = Fellows | first1 = Michael R. | year = 1990 | title = Transversals of vertex partition in graphs | url = | journal = [[SIAM Journal on Discrete Mathematics]] | volume = 3 | issue = | pages = 206–215 }} |
* {{cite journal | doi = 10.1137/0403018 | last1 = Fellows | first1 = Michael R. | year = 1990 | title = Transversals of vertex partition in graphs | url = | journal = [[SIAM Journal on Discrete Mathematics]] | volume = 3 | issue = | pages = 206–215 }} |
Revision as of 18:59, 14 July 2011
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 partition. 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. A graph is strongly k-colorable if, for each partition of the vertices into sets of size k, it admits a strong coloring.
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 (Haxell)
- Asymptotically, sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). (Haxell)
Here Δ(G) is the maximum degree.
Strong chromatic number was independently introduced by Alon (1988) and Fellows (1990).
References
- Alon, Noga (1988). "The linear arboricity of a graph". Israel J. Math. 62: 311–325. doi:10.1007/BF02783300.
- Alon, Noga (1992). "The strong chromatic number". Random Structures and Algorithms. 3: 1–7. doi:10.1002/rsa.3240030102.
- Fellows, Michael R. (1990). "Transversals of vertex partition in graphs". SIAM Journal on Discrete Mathematics. 3: 206–215. doi:10.1137/0403018.
- Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.