×

zbMATH — the first resource for mathematics

List edge and list total colorings of planar graphs without 4-cycles. (English) Zbl 1108.05038
O. V. Borodin, A. V. Kostochka and D. R. Woodall [J. Comb. Theory, Ser. B 71, 184–204 (1997; Zbl 0876.05032)] proved that if \(G\) is a simple planar graph with maximum degree \(\Delta \geq 12\) then the list edge chromatic number \( \chi _{\mathrm{list}}^{\prime }(G)=\Delta \) and the list total chromatic number \(\chi _{\mathrm{list}}^{\prime \prime }(G)=\Delta +1\).
In the paper under review these equalities are shown to hold for a planar graph \(G\) which satisfies one of the following conditions: \(\Delta \geq 7\) and \(G\) has no cycle of length 4, \(\Delta =6\) and \(G\) has no cycle of length 4 or 5, or \( \Delta =5\) and \(G\) has no cycle whose length lies in the closed interval \( [4,8]\). In addition, \(\chi _{\mathrm{list}}^{\prime }(G)=\Delta \) is shown to hold for a planar graph \(G\) with \(\Delta =4\) if \(G\) has no cycle whose length lies in the closed interval \([4,14]\).

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan Press London · Zbl 1134.05001
[2] Borodin, O.V.; Kostochka, A.V.; Woodall, D.R., List edge and List total colorings of multigraphs, J. combin. theory ser. B, 71, 184-204, (1997) · Zbl 0876.05032
[3] Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory ser. B, 63, 153-158, (1995) · Zbl 0826.05026
[4] 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
[5] Ha˝ggkvist, R.; Janssen, J., Now bounds on the List-chromatic index of the complete graph and other simple graphs, Combin. probab. comput., 6, 295-313, (1997) · Zbl 0880.05035
[6] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley-Interscience New York · Zbl 0971.05046
[7] Lam, P.C.B.; Shiu, W.C.; Xu, B., On structure of some plane graphs with application to choosability, J. combin. theory ser. B, 82, 285-296, (2001) · Zbl 1024.05049
[8] Peterson, D.; Woodall, D.R., Edge-choosability in line-perfect multigraphs, Discrete math., 202, 191-199, (1999) · Zbl 0928.05017
[9] Wang, W.F.; Lih, K.W., Edge-choosability and total choosability of outerplane graphs, European J. combin., 22, 71-78, (2001) · Zbl 0972.05021
[10] Wang, P.; Wu, J.L., A note on total colorings of planar graphs without 4-cycles, Discuss. math. graph theory, 24, 125-135, (2004) · Zbl 1056.05067
[11] Woodall, D.R., Edge-choosability of multicircuits, Discrete math., 202, 271-277, (1999) · Zbl 0928.05018
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.