zbMATH — the first resource for mathematics

Choice numbers of graphs: A probabilistic approach. (English) Zbl 0793.05076
Summary: The choice number of a graph \(G\) is the minimum integer \(k\) such that for every assignment of a set \(S(v)\) of \(k\) colors to every vertex \(v\) of \(G\), there is a proper coloring of \(G\) that assigns to each vertex \(v\) a color from \(S(v)\). By applying probabilistic methods, it is shown that there are two positive constants \(c_ 1\) and \(c_ 2\) such that for all \(m\geq 2\) and \(r\geq 2\) the choice number of the complete \(r\)-partite graph with \(m\) vertices in each vertex class is between \(c_ 1 r\log m\) and \(c_ 2 r\log m\). This supplies the solutions of two problems of P. Erdős, A. L. Rubin and H. Taylor [Combinatorics, graph theory and computing, Proc. West Coast Conf., Arcata/Calif. 1979, 125-157 (1980; Zbl 0469.05032)], as it implies that the choice number of almost all the graphs on \(n\) vertices is \(o(n)\) and that there is an \(n\) vertex graph \(G\) such that the sum of the choice number of \(G\) with that of its complement is at most \(O(n^{1/2}(\log n)^{1/2})\).

05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Vizing, Metody Diskret. Anal. v. Teorii Kodov i Shem 101 pp 3– (1976)
[2] Erd?s, Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI pp 125– (1979)
[3] DOI: 10.1002/jgt.3190130112 · Zbl 0674.05026 · doi:10.1002/jgt.3190130112
[4] DOI: 10.1002/rsa.3240030102 · Zbl 0751.05034 · doi:10.1002/rsa.3240030102
[5] DOI: 10.1007/BF02122551 · Zbl 0666.05033 · doi:10.1007/BF02122551
[6] Alon, Colorings and orientations of graphs · Zbl 0756.05049 · doi:10.1007/BF01204715
[7] Alon, The Probabilistic Method (1991)
[8] Bollobás, Random Graphs (1985)
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.