zbMATH — the first resource for mathematics

List edge and list total colourings of multigraphs. (English) Zbl 0876.05032
This paper exploits the remarkable new method of F. Galvin [J. Comb. Theory, Ser. B 63, No. 1, 153-158 (1995; Zbl 0826.05026)], who proved that the list edge chromatic number \(\chi_{\text{list}}'(G)\) of a bipartite multigraph \(G\) equals its edge chromatic number \(\chi'(G)\). It is now proved here that if every edge \(e= uw\) of a bipartite multigraph \(G\) is assigned a list of at least \(\max\{d(u),d(w)\}\) colours, then \(G\) can be edge-coloured with each edge receiving a colour from its list. If every edge \(e=uw\) in an arbitrary multigraph \(G\) is assigned a list of at least \(\max\{d(u),d(w)\}+ \lfloor{1\over 2}\min\{d(u),d(w)\}\rfloor\) colours, then the same holds; in particular, if \(G\) has maximum degree \(\Delta=\Delta(G)\) then \(\chi_{\text{list}}'(G)\leq\lfloor{3\over 2}\Delta\rfloor\). Sufficient conditions are given in terms of the maximum degree and maximum average degree of \(G\) in order that \(\chi_{\text{list}}'(G)=\Delta\) and \(\chi''_{\text{list}}(G)= \Delta+1\). Consequences are deduced for planar graphs in terms of their maximum degree and girth, and it is also proved that if \(G\) is a simple planar graph and \(\Delta\geq 12\) then \(\chi_{\text{list}}'(G)=\Delta\) and \(\chi''_{\text{list}}(G)=\Delta+1\).

05C15 Coloring of graphs and hypergraphs
PDF BibTeX Cite
Full Text: DOI
[1] M. Behzad, 1965, Graphs and Their Chromatic Numbers
[2] Bollobás, B.; Hind, H.R., A new upper bound for the List chromatic number, Discrete math., 74, 65-75, (1989) · Zbl 0674.05027
[3] O. V. Borodin, 1977, Criterion of chromaticity of a degree prescription, Abstracts of IV All-Union Conference on Theoretical Cybernetics, 127, 128
[4] O. V. Borodin, 1979, Problems of Colouring and of Covering the Vertex Set of a Graph by Induced Subgraphs, Novosibirsk
[5] Borodin, O.V., On the total coloring of planar graphs, J. reine angew. math., 394, 180-185, (1989) · Zbl 0653.05029
[6] Borodin, O.V., An extension of Kotzig’s theorem and the List edge colouring of planar graphs, Mat. zametki, 48, 22-28, (1990)
[7] O. V. Borodin, A. V. Kostochka, D. R. Woodall, Total colourings of planar graphs with large girth · Zbl 0886.05065
[8] O. V. Borodin, A. V. Kostochka, D. R. Woodall, Total colourings of planar graphs with large maximum degree, J. Graph Theory · Zbl 0883.05053
[9] Chen, D.L.; Wu, J.L., The total coloring of some graphs, Combinatorics graph theory, algorithms, and applications, Beijing, 1993, (1994), World Science River Edge, p. 17-20
[10] Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)
[11] Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory ser. B, 63, 153-158, (1995) · Zbl 0826.05026
[12] Gupta, R.P., The chromatic index and the degree of a graph, Notices amer. math. soc., 13, (1966), abstract 66T-429
[13] Häggkvist, R.; Chetwynd, A., Some upper bounds on the total and List chromatic numbers of multigraphs, J. graph theory, 16, 503-516, (1992) · Zbl 0814.05038
[14] Häggkvist, R.; Janssen, J., New bounds on the List-chromatic index of the complete graph and other simple graphs, Res. rep., 19, (1993)
[15] Hind, H.R., Ph.D. thesis, (1988)
[16] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley-Interscience New York · Zbl 0971.05046
[17] Kahn, J., Recent results on some not-so-recent hypergraph matching and covering problems, Extremal problems for finite sets, visegrád, 1991, Bolyai society math. studies, 3, (1994), János Bolyai Math. Soc Budapest, p. 305-353 · Zbl 0820.05050
[18] Kahn, J., Asymptotically good List-colorings, J. combin. theory ser. A, 73, 1-59, (1996) · Zbl 0851.05081
[19] J. Kahn, Asymptotics of the list-chromatic index for multigraphs · Zbl 0956.05038
[20] Kostochka, A.V., An analogue of Shannon’s estimate for complete colorings, Metody diskret anal., 30, 13-22, (1977) · Zbl 0424.05026
[21] Kostochka, A.V., The total coloring of a multigraph with maximal degree 4, Discrete math., 17, 161-163, (1977) · Zbl 0411.05038
[22] A. V. Kostochka, Exact upper bound for the total chromatic number of a graph, Proc. 24th International Wiss. Koll, Tech. Hochsch. Ilmenau, 1979, 33, 36
[23] Kostochka, A.V., The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete math., 162, 199-214, (1996) · Zbl 0871.05023
[24] Rosenfeld, M., On the total coloring of certain graphs, Israel J. math., 9, 396-402, (1971) · Zbl 0211.56604
[25] Shannon, C.E., A theorem on coloring the lines of a network, J. math. phys., 28, 148-151, (1948) · Zbl 0032.43203
[26] Slivnik, T., A short proof of Galvin’s theorem on the List-chromatic index of a bipartite multigraph, Combin. probab. comput., 5, 91-94, (1996) · Zbl 0857.05034
[27] Tutte, W.T., The factors of graphs, Canad. J. math., 4, 314-328, (1952) · Zbl 0049.24202
[28] Vijayaditya, N., On total chromatic number of a graph, J. London math. soc. (2), 3, 405-408, (1971) · Zbl 0223.05103
[29] Vizing, V.G., On an estimate of the chromatic class of ap, Metody diskret anal., 3, 25-30, (1964) · Zbl 1249.05144
[30] Vizing, V.G., Critical graphs with given chromatic class, Metody diskret analiz., 5, 9-17, (1965)
[31] Vizing, V.G., Some unsolved problems in graph theory, Uspekhi mat. nauk, 23, 117-134, (1968) · Zbl 0177.52301
[32] Vizing, V.G., Vertex colorings with given colors, Metody diskret. anal., 29, 3-10, (1976) · Zbl 1249.90303
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.