×

zbMATH — the first resource for mathematics

Asymptotics of the list-chromatic index for multigraphs. (English) Zbl 0956.05038
Author’s abstract: The list-chromatic index, \(\chi'_{l}(G)\), of a multigraph \(G\) is the least \(t\) such that if \(S(A)\) is a set of size \(t\) for each \(A\in E(G)\), then there exists a proper coloring \(\sigma \) of \(G\) with \(\sigma (A)\in S(A)\) for each \(A\in E(G)\). The list-chromatic index is bounded below by the ordinary chromatic index, \(\chi '(G)\), which in turn is at least the fractional chromatic index, \(\chi ^{\prime*}(G)\). In previous work we showed that the chromatic and fractional chromatic indices are asymptotically the same; here we extend this to the list-chromatic index: \(\chi '_{l}(G)\sim \chi ^{\prime*}(G)\) as \(\chi '_{l}(G)\rightarrow \infty \). The proof uses sampling from “hard-core” distributions on the set of matchings of a multigraph to go from fractional to list coloring.

MSC:
05C15 Coloring of graphs and hypergraphs
60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ajtai, Europ J Combinatorics 2 pp 1– (1981)
[2] ? Restricted colorings of graphs,? Surveys in Combinatorics, 1993 (Proc. 14th British Combinatorial Conf.), Cambridge Univ. Press, Cambridge, 1993, pp. 1-33. · doi:10.1017/CBO9780511662089.002
[3] and The Probabilistic Method, Wiley, New York, 1992.
[4] Alon, Combinatorica 12 pp 125– (1992)
[5] Andersen, Math Scand 40 pp 161– (1977)
[6] van den Berg, Stochastic Processes Appl. 49 pp 179– (1994)
[7] ? Martingales, isoperimetric inequalities and random graphs,? Combinatorics, and (Editors), Colloq. Math. Soc. János Bolyai 52, North Holland Amsterdam 1988.
[8] Bollobás, Graphs Combinatorics 1 pp 115– (1985)
[9] Edmonds, J Res Nat Bureau of Standards (B) 69 pp 125– (1965) · Zbl 0141.21802 · doi:10.6028/jres.069B.013
[10] Erd?s, Congressus Numerantium 23 pp 19– (1979)
[11] Erd?s, Coll Math Soc J Bolyai 10 pp 609– (1974)
[12] Erd?s, Congressus Numerantium 26 pp 125– (1979)
[13] Erd?s, Discr Appl Math 30 pp 151– (1990)
[14] Frankl, Europ J Combinatorics 6 pp 317– (1985) · Zbl 0624.05055 · doi:10.1016/S0195-6698(85)80045-7
[15] Füredi, Graphs Combinatorics 4 pp 115– (1988)
[16] Galvin, J Combinatorial Th (B) 63 pp 153– (1995)
[17] Godsil, J Graph Th 5 pp 285– (1981)
[18] Goldberg, Diskret Analiz 23 pp 3– (1973)
[19] and On the list-chromatic index of bipartite graphs, manuscript, 1993.
[20] Heilmann, Phys Rev Lett 24 pp 1412– (1970)
[21] Heilmann, Comm Math Phys 25 pp 190– (1972)
[22] Restricted edge-colourings, Doctoral thesis, Peterhouse College, Cambridge, 1988.
[23] Janssen, Bull Amer Math Soc 29 pp 243– (1993)
[24] An improved upper bound on the choice number for triangle free graphs, manuscript, 1994.
[25] Kahn, J Combinatorial Th (A) 59 pp 31– (1992)
[26] ? Recent results on some not-so-recent hypergraph matching and covering problems,? Extremal Problems for Finite Sets, Visegrád, 1991, Bolyai Soc. Math. Studies, János Bolyai Math. Soc., Budapest, Vol. 3, 1994, pp. 305-353.
[27] Kahn, J Combinatorial Th (A) 73 pp 1– (1996)
[28] ? On some hypergraph problems of Paul Erd?s and the asymptotics of matchings, covers and colorings,? The Mathematics of Paul Erd?s, Vol. 1, Springer, Berlin, 1997, pp. 345-371. · Zbl 0865.05056
[29] Kahn, Random Struct Algorithms 8 pp 149– (1996)
[30] Kahn, J Combinatorial Th (B) 68 pp 233– (1996)
[31] Kahn, Combinatorica 7 pp 369– (1997)
[32] Kahn, J Combinatorial Th (A) 78 pp 199– (1997)
[33] Kahn, Combinatorica 18 pp 201– (1998)
[34] Kim, Combinatorics, Probability Computing 4 pp 97– (1995) · Zbl 0833.05030 · doi:10.1017/S0963548300001528
[35] Kim, Random Struct Algorithms 7 pp 173– (1995)
[36] König, Math Ann 77 pp 453– (1916)
[37] König, Math Termész Ért 34 pp 104– (1916)
[38] Kunz, Phys Lett (A) pp 311– (1970)
[39] ? Some recent results on convex polytopes,? Contemporary Mathematics, AMS, Providence, RI, 1990, pp. 3-19.
[40] Convex polytopes, the moment map, and canonical convex combinations, manuscript, 1994.
[41] Interacting Particle Systems, Springer, New York, 1985. · doi:10.1007/978-1-4613-8542-4
[42] Stochastic Networks: Complexity, Dependence and Routing, Thesis, Cambridge University, 1990.
[43] and Matching Theory, North Holland, Amsterdam, 1986.
[44] On the method of bounded differences, Surveys in Combinatorics 1989, Invited Papers at the 12th British Combinatorial Conference, (Editor), Cambridge University Press, Cambridge, 1989, pp. 148-188. · doi:10.1017/CBO9781107359949.008
[45] and Asymptotic Theory of Finite Dimensional Normed Spaces, Springer, Berlin, 1980.
[46] and ? An upper bound on the chromatic index of multigraphs,? Graph Theory with Applications to Algorithms and Computer Science et al. (Editors), Wiley, New York, 1985.
[47] Nishizeki, SIAM J Disc Math 3 pp 391– (1990)
[48] unpublished (see [45], [15]).
[49] Pippenger, J Combinatorial Th (A) 51 pp 24– (1989)
[50] and Quadratic Dynamical Systems, Proc. 33rd IEEE Symposium on Foundations of Computer Science, IEEE, Los Alamitos, CA, 1992, pp. 304-313.
[51] Rödl, Europ J Combinatorics 5 pp 69– (1985) · Zbl 0565.05016 · doi:10.1016/S0195-6698(85)80023-8
[52] Theory of Linear and Integer Programming, Wiley, Chichester, 1986.
[53] ? Some unsolved problems on one-factorizations of graphs,? Graph Theory and Related Topics, and (Editors), Academic Press, New York, 1979.
[54] Shannon, J Math Phys 28 pp 148– (1949) · Zbl 0032.43203 · doi:10.1002/sapm1949281148
[55] Lecture notes, M.I.T., 1987.
[56] Spencer, Random Struct Algorithms 7 pp 167– (1995)
[57] Talagrand, Publ Math IHES 81 pp 73– (1995) · Zbl 0864.60013 · doi:10.1007/BF02699376
[58] Vizing, Diskret Analiz 3 pp 25– (1964)
[59] Vizing, Kibernetica (Kiev) 3 pp 29– (1965)
[60] Vizing, Diskret Analiz No 29 MetodyDiskret Anal v Teorii Kodov i Shem 101 pp 3– (1976)
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.