zbMATH — the first resource for mathematics

The strong chromatic number of a graph. (English) Zbl 0751.05034
Let $$G=(V,E)$$ be a graph of $$n$$ vertices. If $$k$$ divides $$n$$, then $$G$$ is said to be strongly $$k$$-colorable if for any partition of $$V$$ into pairwise disjoint sets $$V_ i$$, each of cardinality $$k$$, there is a proper $$k$$-vertex coloring of $$G$$ in which each color meets $$V_ i$$, $$i=1,2,\ldots,n/k$$, in exactly one vertex. If $$k$$ does not divide $$n$$, then $$G$$ is said to be strongly $$k$$-colorable if the graph obtained from $$G$$ by adding to it $$k\lceil n/k\rceil-n$$ isolated vertices is strongly $$k$$-colorable. The author shows that there is an absolute constant $$c$$ such that for any graph with vertex maximum degree $$d$$, the strongly chromatic number is less than or equal to $$cd$$.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text:
References:
 [1] Alon, The linear arboricity of graphs, Isr. J. Math. 62 pp 311– (1988) · Zbl 0673.05019 [2] Alon, A parallel algorithmic version of the Local Lemma, Random Struct. Alg. 2 pp 367– (1991) · Zbl 0768.05086 [3] Beck, An algorithmic approach to the Lovász Local Lemma I, Random Struct. Alg. 2 pp 343– (1991) [4] Bollobás, Extremal Graph Theory (1978) [5] Erdös, Colloq. Math. Soc. J. Bolyai 11, in: Infinite and Finite Sets pp 609– (1975) [6] Fellows, Transversals of vertex partitions in graphs, SIAM J. Discrete Math. 3 pp 206– (1990) · Zbl 0735.05057 [7] Hajnal, Colloq. Math. Soc. J. Bolyai II, in: Combinatorial Theory and its Applications pp 601– (1970) [8] Spencer, Ten Lectures on the Probabilistic Method (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.