×

zbMATH — the first resource for mathematics

An introduction to the discharging method via graph coloring. (English) Zbl 1355.05104
Summary: We provide a “how-to” guide to the use and application of the discharging method. Our aim is not to exhaustively survey results proved by this technique, but rather to demystify the technique and facilitate its wider use, using applications in graph coloring as examples. Along the way, we present some new proofs and new problems.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C07 Vertex degrees
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Agnarsson, G.; Halldórsson, M. M., Coloring powers of planar graphs, SIAM J. Discrete Math., 16, 4, 651-662, (2003) · Zbl 1029.05047
[2] Akiyama, J.; Exoo, G.; Harary, F., Covering and packing in graphs III: cyclic and acyclic invariants, Math Slovaca, 30, 405-417, (1980) · Zbl 0458.05050
[3] Akiyama, J.; Exoo, G.; Harary, F., Covering and packing in graphs. IV. linear arboricity, Networks, 11, 1, 69-72, (1981) · Zbl 0479.05027
[4] Albertson, M. O., A lower bound for the independence number of a planar graph, J. Combin. Theory Ser. B, 20, 1, 84-93, (1976) · Zbl 0286.05105
[5] Albertson, M. O.; Chappell, G. G.; Kierstead, H. A.; Kündgen, A.; Ramamurthi, R., Coloring with no 2-colored \(P_4\)’s, Electron. J. Combin., 11, 1, (2004), Research Paper 26, 13 pp · Zbl 1053.05045
[6] Alon, N., The linear arboricity of graphs, Israel J. Math., 62, 311-325, (1988) · Zbl 0673.05019
[7] Appel, K.; Haken, W., Every planar map is four colorable. I. discharging, Illinois J. Math., 21, 3, 429-490, (1977) · Zbl 0387.05009
[8] Appel, K.; Haken, W., Every planar map is four colorable, with the collaboration of J. Koch, (Contemporary Mathematics, vol. 98, (1989), American Mathematical Society Providence, RI), xvi+741 pp
[9] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable. II. reducibility, Illinois J. Math., 21, 3, 491-567, (1977) · Zbl 0387.05010
[10] Balogh, J.; Kochol, M.; Pluhár, A.; Yu, X., Covering planar graphs with forests, J. Combin. Theory Ser. B, 94, 1, 147-158, (2005) · Zbl 1059.05081
[11] Bollobás, B.; Harris, A. J., List-colourings of graphs, Graphs Combin., 1, 115-127, (1985) · Zbl 0606.05027
[12] Bonamy, M., Planar graphs with \(\Delta \geq 8\) are \((\Delta + 1)\)-edge-choosable, SIAM J. Discrete Math., 29, 3, 1735-1763, (2015) · Zbl 1321.05061
[13] Bonamy, M.; Lévêque, B.; Pinlou, A., \(2\)-distance coloring of sparse graphs, J. Graph Theory, 77, 3, 190-218, (2014) · Zbl 1304.05042
[14] Bonamy, M.; Lévêque, B.; Pinlou, A., List coloring the square of sparse graphs with large degree, European J. Combin., 41, 128-137, (2014) · Zbl 1300.05090
[15] Bonamy, M.; Lévêque, B.; Pinlou, A., Graphs with maximum degree \(D\) at least \(17\) and maximum average degree less than 3 are List 2-distance \((D + 2)\)-colorable, Discrete Math., 317, 19-32, (2014) · Zbl 1279.05020
[16] Borodin, O. V., On acyclic colorings of planar graphs, Discrete Math., 25, 3, 211-236, (1979) · Zbl 0406.05031
[17] Borodin, O. V., On the total coloring of planar graphs, J. Reine Angew. Math., 394, 180-185, (1989) · Zbl 0653.05029
[18] Borodin, O. V., Solving the kotzig and grünbaum problems on the separability of a cycle in planar graphs, Mat. Zametki, 46, 5, 9-12, 103, (1989), (in Russian). Translation in Math. Notes 46 (5-6) (1990), 835-837 · Zbl 0694.05027
[19] Borodin, O. V., A generalization of kotzig’s theorem and prescribed edge coloring of planar graphs, Mat. Zametki, 48, 6, 22-28, 160, (1990), (in Russian). Translation in Math. Notes 48 (5-6) (1991), 1186-1190
[20] Borodin, O. V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. Graph Theory, 21, 2, 183-186, (1996) · Zbl 0838.05039
[21] Borodin, O. V., Structural theorem on plane graphs with application to the entire coloring number, J. Graph Theory, 23, 3, 233-239, (1996) · Zbl 0863.05035
[22] Borodin, O. V., Colorings of plane graphs: A survey, Discrete Math., 313, 4, 517-539, (2013) · Zbl 1259.05042
[23] Borodin, O. V.; Broersma, H. J.; Glebov, A.; van den Heuvel, J., Stars and bunches in planar graphs, part II: general planar graphs and colourings, (CDAM Research Report Series, 2002-05, (2002)), Original Russian version. Diskretn. Anal. Issled. Oper. Ser. 1 8 (4) (2001), 9-33. Available at: http://www.cdam.lse.ac.uk/Reports/Abstracts/cdam-2002-05.html · Zbl 1012.05074
[24] Borodin, O. V.; Chen, M.; Ivanova, A. O.; Raspaud, A., Acyclic 3-choosability of sparse graphs with girth at least 7, Discrete Math., 310, 17-18, 2426-2434, (2010) · Zbl 1213.05049
[25] Borodin, O. V.; Fon-Der Flaass, D. G.; Kostochka, A. V.; Raspaud, A.; Sopena, E., Acyclic List 7-coloring of planar graphs, J. Graph Theory, 40, 2, 83-90, (2002) · Zbl 1004.05029
[26] Borodin, O. V.; Glebov, A. N.; Ivanova, A. O.; Neustroeva, T. K.; Tashkinov, V. A., Sufficient conditions for planar graphs to be 2-distance \((\Delta + 1)\)-colorable, Sib. Élektron. Mat. Izv., 1, 129-141, (2004), English summary (in Russian) · Zbl 1076.05032
[27] Borodin, O. V.; Glebov, A. N.; Raspaud, A.; Salavatipour, M. R., Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B, 93, 2, 303-311, (2005) · Zbl 1056.05052
[28] Borodin, O. V.; Hartke, S. G.; Ivanova, A. O.; Kostochka, A. V.; West, D. B., Circular (5,2)-coloring of sparse graphs, Sib. Èlektron. Mat. Izv., 5, 417-426, (2008) · Zbl 1299.05115
[29] Borodin, O. V.; Ivanova, A. O., 2-distance \((\Delta + 2)\)-coloring of planar graphs with girth six and \(\Delta \geq 18\), Discrete Math., 309, 23-24, 6496-6502, (2009) · Zbl 1184.05040
[30] Borodin, O. V.; Ivanova, A. O., List 2-distance \((\Delta + 2)\)-coloring of planar graphs with girth six, European J. Combin., 30, 5, 1257-1262, (2009) · Zbl 1190.05055
[31] Borodin, O. V.; Ivanova, A. O., List 2-distance \((\Delta + 2)\)-coloring of planar graphs with girth six and \(\Delta \geq 24\), Sibirsk. Mat. Zh., 50, 6, 1216-1224, (2009), (in Russian). Translation in Sib. Math. J. 50 (6) (2009), 958-964 · Zbl 1224.05159
[32] Borodin, O. V.; Ivanova, A. O., Almost proper vertex 2-colorings of sparse graphs, Diskretn. Anal. Issled. Oper., 16, 2, 16-20, 98, (2009), Translation in J. Appl. Ind. Math. 4 (1) (2010) 21-23 · Zbl 1249.05110
[33] Borodin, O. V.; Ivanova, A. O., Acyclic 5-choosability of planar graphs without 4-cycles, Sibirsk. Mat. Zh., 52, 3, 522-541, (2011), (in Russian). Translation in Sib. Math. J. 52 (3) (2011), 411-425 · Zbl 1294.05057
[34] Borodin, O. V.; Ivanova, A. O., Acyclic 5-choosability of planar graphs without adjacent short cycles, J. Graph Theory, 68, 2, 169-176, (2011) · Zbl 1235.05038
[35] Borodin, O. V.; Ivanova, A. O., Acyclic 4-choosability of planar graphs with no 4- and 5-cycles, J. Graph Theory, 72, 374-397, (2013) · Zbl 1261.05013
[36] Borodin, O. V.; Ivanova, A. O., Describing 3-faces in normal plane maps with minimum degree 4, Discrete Math., 313, 23, 2841-2847, (2013) · Zbl 1281.05054
[37] Borodin, O. V.; Ivanova, A. O., Describing \((d - 2)\)-stars at \(d\)-vertices, \(d \leq 5\), in normal plane maps, Discrete Math., 313, 17, 1700-1709, (2013) · Zbl 1277.05044
[38] Borodin, O. V.; Ivanova, A. O.; Neustroeva, T. K., Sufficient conditions for planar graphs with girth 6 to be 2-distance colourable, Sib. Elektron. Mat. Izv., 3, 441-450, (2006), (in Russian). Available at: http://semr.math.nsc.ru/v3.html · Zbl 1119.05039
[39] Borodin, O. V.; Kim, S.-J.; Kostochka, A. V.; West, D. B., Homomorphisms from sparse graphs with large girth, J. Combin. Theory Ser. B, 90, 1, 147-159, (2004) · Zbl 1033.05037
[40] Borodin, O. V.; Kostochka, A. V.; Woodall, D. R., List edge and List total colourings of multigraphs, J. Combin. Theory Ser. B, 71, 2, 184-204, (1997) · Zbl 0876.05032
[41] Borodin, O. V.; Sanders, D., On light edges and triangles in planar graphs of minimum degree five, Math. Nachr., 170, 19-24, (1994) · Zbl 0813.05020
[42] Brandt, A.; Ferrara, M.; Kumbhat, M.; Loeb, S.; Stolee, D.; Yancey, M., I,F-partitions of sparse graphs, European J. Combin., 57, 1-12, (2016) · Zbl 1339.05300
[43] Brooks, R. L., On colouring the nodes of a network, Proc. Cambridge Philos. Soc., 37, 194-197, (1941) · Zbl 0027.26403
[44] Bu, Y.; Cranston, D.; Montassier, M.; Raspaud, A.; Wang, W., Star coloring of sparse graphs, J. Graph Theory, 62, 3, 201-219, (2009) · Zbl 1179.05042
[45] Bu, Y.; Wang, W., Some sufficient conditions for a planar graph of maximum degree six to be class 1, Discrete Math., 306, 13, 1440-1445, (2006) · Zbl 1095.05014
[46] Chen, M.; Raspaud, A., Planar graphs without 4- and 5-cycles are acyclically 4-choosable, Discrete Appl. Math., 161, 7-8, 921-931, (2013) · Zbl 1262.05029
[47] Chen, M.; Raspaud, A.; Wang, W., 8-star-choosability of a graph with maximum average degree less than \(3\), Discrete Math. Theor. Comput. Sci., 13, 3, 97-110, (2011) · Zbl 1283.05087
[48] Chen, M.; Raspaud, A.; Wang, W., 6-star-coloring of subcubic graphs, J. Graph Theory, 72, 2, 128-145, (2013) · Zbl 1259.05057
[49] Cohen, N.; Havet, F., Planar graphs with maximum degree \(\Delta \geq 9\) are \((\Delta + 1)\)-edge-choosable—a short proof, Discrete Math., 310, 21, 3049-3051, (2010) · Zbl 1208.05016
[50] Cohen-Addad, V.; Hebdige, M.; Král’, D.; Li, Z.; Salgado, E., Steinberg’s conjecture is false, J. Combin. Theory Ser. (B), (2016) · Zbl 1350.05018
[51] Cranston, D. W., Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles, Discuss. Math. Graph Theory, 29, 1, 163-178, (2009) · Zbl 1198.05044
[52] Cranston, D. W.; Erman, R.; Škrekovski, R., Choosability of the square of a planar graph with maximum degree four, Australas. J. Combin., 59, 86-97, (2014) · Zbl 1296.05053
[53] Cranston, D. W.; Jahanbekam, S.; West, D. B., The 1,2,3-conjecture and 1,2-conjecture for sparse graphs, Discuss. Math. Graph Theory, 34, 4, 769-799, (2014) · Zbl 1303.05172
[54] Cranston, D. W.; Kim, S.-J., List-coloring the square of a subcubic graph, J. Graph Theory, 57, 1, 65-87, (2008) · Zbl 1172.05023
[55] Cranston, D. W.; Kim, S.-J.; Yu, G., Injective colorings of sparse graphs, Discrete Math., 310, 21, 2965-2973, (2010) · Zbl 1209.05075
[56] Cranston, D. W.; Kim, S.-J.; Yu, G., Injective colorings of graphs with low average degree, Algorithmica, 60, 3, 553-568, (2011) · Zbl 1218.05046
[57] Cranston, D. W.; Škrekovski, R., Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\), Discrete Appl. Math., 162, 167-176, (2014) · Zbl 1300.05093
[58] Cranston, D. W.; Yu, G., Linear choosability of sparse graphs, Discrete Math., 311, 17, 1910-1917, (2011) · Zbl 1225.05095
[59] Cygan, M.; Kowalik, Ł.; Lužar, B., A planar linear arboricity conjecture, (Algorithms and Complexity, Lecture Notes in Comput. Sci., vol. 6078, (2010), Springer), 204-216 · Zbl 1284.05211
[60] Dvořák, Z.; Kawarabayashi, K.; Thomas, R., Three-coloring triangle-free planar graphs in linear time, (Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (Extended Abstract), (2009), SIAM Philadelphia, PA), ACM Trans. Algorithms, 7, 4, 1176-1182, (2011), Art. 41, 14 pp · Zbl 1423.05064
[61] Dvořák, Z.; Král’, D.; Nejedlý, P.; Škrekovski, R., Coloring squares of planar graphs with girth six, European J. Combin., 29, 4, 838-849, (2008) · Zbl 1143.05027
[62] Enomoto, H.; Péroche, B., The linear arboricity of some regular graphs, J. Graph Theory, 8, 309-324, (1984) · Zbl 0581.05017
[63] Erdős, P.; Rényi, A., On a problem in the theory of graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., 7, 623-641, (1962), (in Hungarian)
[64] Erdős, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, (Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., vol. 26, (1980), Utilitas Math.), 125-157
[65] Esperet, L.; van den Heuvel, J.; Maffray, F.; Sipma, F., Fire containment in planar graphs, J. Graph Theory, 73, 3, 267-279, (2013) · Zbl 1269.05026
[66] Fertin, G.; Raspaud, A.; Reed, B., Star coloring of graphs, J. Graph Theory, 47, 3, 163-182, (2004) · Zbl 1055.05051
[67] Fiorini, S., Some remarks on a paper by vizing on critical graphs, Math. Proc. Cambridge Philos. Soc., 77, 475-483, (1975) · Zbl 0306.05120
[68] Franklin, P., The four color problem, Amer. J. Math., 44, 3, 225-236, (1922) · JFM 48.0664.02
[69] Galvin, F., The List chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B, 63, 1, 153-158, (1995) · Zbl 0826.05026
[70] Grötzsch, H., Ein dreifarbensatz für dreikreisfreie netze auf der kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 8, 109-120, (1959), (in German)
[71] Grünbaum, B., Acyclic colorings of planar graphs, Israel J. Math., 14, 390-408, (1973) · Zbl 0265.05103
[72] Guldan, F., The linear arboricity of \(10\)-regular graphs, Math. Slovaca, 36, 225-228, (1986) · Zbl 0612.05050
[73] Gupta, R. P., The chromatic index and the degree of a graph, Notices Amer. Math. Soc., 13, (1966), abstract 66T-429
[74] S.G. Hartke, S. Jahanbekam, B. Thomas, The chromatic number of the square of subcubic planar graphs. http://arxiv.org/abs/1604.06504.
[75] F. Havet, J. van den Heuvel, C. McDiarmid, B. Reed, List colouring squares of planar graphs, preprint, available at: http://arxiv.org/abs/0807.3233. · Zbl 1341.05073
[76] Havet, F.; Sereni, J.-S., Improper choosability of graphs and maximum average degree, J. Graph Theory, 52, 3, 181-199, (2006) · Zbl 1104.05026
[77] Hell, P.; Seyffarth, K., Largest planar graphs of diameter two and fixed maximum degree, Discrete Math., 111, 1-3, 313-322, (1993) · Zbl 0837.05074
[78] van den Heuvel, J.; McGuinness, S., Coloring the square of a planar graph, J. Graph Theory, 42, 2, 110-124, (2003) · Zbl 1008.05065
[79] Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 4, 718-720, (1981) · Zbl 0473.68034
[80] Ivanova, A. O., List \(2\)-distance \((\Delta + 1)\)-coloring of sparse planar graphs with girth at least \(7\), Diskretn. Anal. Issled. Oper., J. Appl. Indust. Math., 5, 5, 221-230, (2011), 94 (in Russian)
[81] Jaeger, F., Nowhere-zero flow problems, (Beineke, L.; etal., Selected Topics in Graph Theory, vol. 3, (1988), Academic Press), 91-95
[82] Jendrol’, S., A short proof of kotzig’s theorem on minimal edge weights of convex 3-polytopes, (Balint, V., Proc. Intl. Scient. Conf. Math., Žilina. 1998, (1999), EDIS Univ. Press Žilina), 35-38 · Zbl 0938.52010
[83] Jendrol’, S.; Voss, H.-J., Light subgraphs of graphs embedded in the plane-A survey, Discrete Math., 313, 4, 406-421, (2013) · Zbl 1259.05045
[84] Jonas, T. K., Graph coloring analogues with A condition at distance two: L(2,1)-labellings and List lambda-labellings, (1993), University of South Carolina, 95 pp
[85] Juvan, M.; Mohar, B.; Škrekovski, R., Graphs of degree 4 are 5-edge-choosable, J. Graph Theory, 32, 3, 250-264, (1999) · Zbl 0934.05052
[86] Kahn, J., Asymptotics of the List chromatic index for multigraphs, Random Struct. Algorithms, 17, 2, 117-156, (2000) · Zbl 0956.05038
[87] Kim, S.-J.; Park, W.-J., List dynamic coloring of sparse graphs, (Combinatorial Optimization and Applications, Lecture Notes in Comput. Sci., vol. 6831, (2011), Springer Heidelberg), 156-162 · Zbl 1342.05043
[88] Kim, S.-J.; Park, B., Counterexamples to the List square coloring conjecture, J. Graph Theory, 78, 4, 239-247, (2015) · Zbl 1309.05075
[89] Kostochka, A. V.; Mel’nikov, L. S., Note to the paper of grünbaum on acyclic colorings, Discrete Math., 14, 4, 403-406, (1976) · Zbl 0318.05103
[90] Kostochka, A. V.; Woodall, D. R., Choosability conjectures and multicircuits, Discrete Math., 240, 1-3, 123-143, (2001) · Zbl 0989.05041
[91] Kostochka, A. V.; Yancey, M., Ore’s conjecture for \(k = 4\) and grötzsch’s theorem, Combinatorica, 34, 3, 323-329, (2014) · Zbl 1349.05111
[92] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. Čas SAV (Math. Slovaca), 5, 101-113, (1955), (in Slovak)
[93] Lebesgue, H., Quelques conséquences simples de la formule d’euler, J. Math. Pures Appl., 19, 27-43, (1940), (in French) · JFM 66.0736.03
[94] Lovász, L.; Thomassen, C.; Wu, Y.; Zhang, C.-Q., Nowhere-zero 3-flows and modulo \(k\)-orientations, J. Combin. Theory Ser. B, 103, 587-598, (2013) · Zbl 1301.05154
[95] Luo, R.; Zhang, C.-Q., Edge coloring of graphs with small average degrees, Discrete Math., 275, 207-218, (2004) · Zbl 1030.05040
[96] Miao, L.; Sun, Q., On the size of critical graphs with maximum degree 8, Discrete Math., 310, 2215-2218, (2010) · Zbl 1225.05143
[97] Molloy, M.; Salavatipour, M. R., A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B, 94, 2, 189-213, (2005) · Zbl 1071.05036
[98] Montassier, M., Acyclic 4-choosability of planar graphs with girth at least 5, (Graph Theory in Paris, Trends Math., (2007), Birkhäuser), 299-310 · Zbl 1118.05036
[99] Montassier, M.; Raspaud, A.; Wang, W., Acyclic 4-choosability of planar graphs without cycles of specific lengths, (Topics in Discrete Mathematics, Algorithms Combin., vol. 26, (2006), Springer), 473-491 · Zbl 1120.05034
[100] Nash-Williams, C. St. J.A., Decomposition of finite graphs into forests, J. Lond. Math. Soc., 39, 12, (1964) · Zbl 0119.38805
[101] Przybyło, J.; Woźniak, M., On a 1,2-conjecture, Discrete Math. Theor. Comput. Sci., 12, 101-108, (2010) · Zbl 1250.05093
[102] Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R., The four-colour theorem, J. Combin. Theory Ser. B, 70, 1, 2-44, (1997) · Zbl 0883.05056
[103] Robertson, N.; Seymour, P.; Thomas, R., Hadwiger’s conjecture for \(K_6\)-free graphs, Combinatorica, 13, 279-361, (1993) · Zbl 0830.05028
[104] Sanders, D. P.; Zhao, Y., A note on the three color problem, Graphs Combin., 11, 1, 91-94, (1995) · Zbl 0824.05023
[105] Sanders, D. P.; Zhao, Y., Planar graphs of maximum degree seven are class I, J. Combin. Theory Ser. B, 83, 2, 201-212, (2001) · Zbl 1024.05031
[106] Sanders, D. P.; Zhao, Y., On the size of edge chromatic critical graphs, J. Combin. Theory Ser. B, 86, 2, 408-412, (2002) · Zbl 1029.05062
[107] Sanders, D. P.; Zhao, Y., Coloring edges of graphs embedded in a surface of characteristic zero, J. Combin. Theory Ser. B, 87, 2, 254-263, (2003) · Zbl 1068.05026
[108] Steinberg, R., The state of the three color problem, (Gimbel, J.; Kennedy, J. W.; Quintas, L. V., Quo Vadis, Graph Theory?, Annals of Discrete Mathematics, vol. 55, (1993)), 211-248 · Zbl 0791.05044
[109] Stockmeyer, L., Planar 3-colorability is polynomial complete, ACM SIGACT News, 5, 19-25, (1973)
[110] Thomassen, C., Every planar graph is \(5\)-choosable, J. Combin. Theory Ser. B, 62, 1, 180-181, (1994) · Zbl 0805.05023
[111] Thomassen, C., Grötzsch’s 3-color theorem and its counterparts for the torus and the projective plane, J. Combin. Theory Ser. B, 62, 2, 268-279, (1994) · Zbl 0817.05024
[112] Thomassen, C., 3-List-coloring planar graphs of girth 5, J. Combin. Theory Ser. B, 64, 1, 101-107, (1995) · Zbl 0822.05029
[113] Thomassen, C., A short List color proof of grötzsch’s theorem, J. Combin. Theory Ser. B, 88, 1, 189-192, (2003) · Zbl 1025.05022
[114] Timmons, C., Star coloring high girth planar graphs, Electron. J. Combin., 15, 1, (2008), Research Paper 124, 17 pp · Zbl 1165.05326
[115] Vizing, V. G., On an estimate of the chromatic class of a \(p\)-graph, Metody Diskret. Anal., 3, 25-30, (1964), (in Russian)
[116] Vizing, V. G., Critical graphs with given chromatic class, Metody Diskr. Anal., 5, 9-17, (1965), (in Russian)
[117] Vizing, V. G., The chromatic class of a multigraph, Kibernetika (Kiev), 3, 29-39, (1965), (in Russian). English translation in Cybernetics 1, 32-41 · Zbl 0955.05045
[118] Vizing, V. G., Some unsolved problems in graph theory, Uspekhi Mat. Nauk., 23, 117-134, (1968), (in Russian). English translation in Russian Math. Surveys 23, 125-141 · Zbl 0177.52301
[119] Vizing, V. G., Coloring the vertices of a graph in prescribed colors, (Diskret. Analiz, Metody Diskret. Anal. v Teorii Kodov i Shem, vol. 29, (1976)), 3-10, 101, (in Russian)
[120] Voigt, M., List colourings of planar graphs, Discrete Math., 120, 1-3, 215-219, (1993) · Zbl 0790.05030
[121] Wang, W.; Chen, Y., A sufficient condition for a planar graph to be class 1, Theoret. Comput. Sci., 385, 1-3, 71-77, (2007) · Zbl 1125.68090
[122] Wang, W.; Lih, K.-W., Choosability and edge choosability of planar graphs without five cycles, Appl. Math. Lett., 15, 5, 561-565, (2002) · Zbl 0994.05060
[123] Wang, Y.; Xu, L., A sufficient condition for a plane graph with maximum degree 6 to be class 1, Discrete Appl. Math., 161, 1-2, 307-310, (2013) · Zbl 1254.05060
[124] G. Wegner, Graphs with given diameter and a colouring problem, preprint, University of Dortmund, 1977.
[125] Woodall, D. R., The average degree of an edge-chromatic critical graph II, J. Graph Theory, 56, 3, 194-218, (2007) · Zbl 1137.05037
[126] Woodall, D. R., The average degree of a multigraph critical with respect to edge or total choosability, Discrete Math., 310, 6-7, 1167-1171, (2010) · Zbl 1230.05104
[127] Wu, J.-L., On the linear arboricity of planar graphs, J. Graph Theory, 31, 2, 129-134, (1999) · Zbl 0933.05056
[128] Wu, J.-L.; Wu, Y.-W., The linear arboricity of planar graphs of maximum degree seven is four, J. Graph Theory, 58, 3, 210-220, (2008) · Zbl 1158.05023
[129] M. Yancey, Coloring the square of a sparse graph \(G\) with almost \(\Delta(G)\) colors, preprint, available at: http://arxiv.org/abs/1502.03132. · Zbl 1346.05087
[130] Zhang, L., Every planar graph with maximum degree 7 is of class 1, Graphs Combin., 16, 4, 467-495, (2000) · Zbl 0988.05042
[131] Zhang, L.; Wu, B., Edge choosability of planar graphs without small cycles, Discrete Math., 283, 1-3, 289-293, (2004) · Zbl 1042.05033
[132] Zhu, X., Circular chromatic number: a survey, Discrete Math., 229, 1-3, 371-410, (2001) · Zbl 0973.05030
[133] Zhu, X., Recent developments in circular colouring of graphs, (Topics in Discrete Mathematics, Algorithms Combin., vol. 26, (2006), Springer), 497-550 · Zbl 1127.05046
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.