×

Graph edge coloring: a survey. (English) Zbl 1407.05087

Summary: Graph edge coloring has a rich theory, many applications and beautiful conjectures, and it is studied not only by mathematicians, but also by computer scientists. In this survey, written for the non-expert, we shall describe some main results and techniques and state some of the many popular conjectures in the theory. Besides known results a new basic result about brooms is obtained.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akbari, S., Ghanbari, M., Kano, M., Nikmehr, M.J.: The chromatic index of a graph whose core has maximum degree \[22\]. Electron. J. Comb. 19, #P58 (2012) · Zbl 1243.05083
[2] Akbari, S., Ghanbari, M., Nikmehr, M.J.: The chromatic index of a graph whose core is a cycle of order at most \[1313\]. Graphs Comb. 30, 801-819 (2014) · Zbl 1298.05098 · doi:10.1007/s00373-013-1317-9
[3] Akbari, S., Ghanbari, M., Ozeki, K.: The chromatic index of a claw-free graph whose core has maximum degree \[22\]. Graphs Comb. 31, 805-811 (2015) · Zbl 1318.05023 · doi:10.1007/s00373-014-1417-1
[4] Andersen, L.D.: On edge-colourings of graphs. Math. Scand. 40, 161-175 (1975) · Zbl 0373.05035 · doi:10.7146/math.scand.a-11685
[5] Asplund, J., McDonald, J.: On a limit of the method of Tashkinov trees for edge-colouring. Discrete Math. 339, 2231-2238 (2016) · Zbl 1338.05072 · doi:10.1016/j.disc.2016.03.025
[6] Bej, S., Steffen, E.: Factors of edge-chromatic critical graphs: a brief survey and some equivalences. Lect. Notes Semin. Interdiscip. Mat. 14, 37-48 (2017) · Zbl 1373.05058
[7] Belcastro, S.M., Haas, R.: Counting edge-Kempe-equivalence classes for \[33\]-edge-colored cubic graphs. Discrete Math. 325, 77-84 (2014) · Zbl 1288.05081 · doi:10.1016/j.disc.2014.02.014
[8] Belcastro, S.M., Haas, R.: Edge-Kempe-equivalence graphs of class-\[11\] regular graphs. Aust. J. Comb. 62, 197-2014 (2017) · Zbl 1375.05083
[9] Bismarck de Sousa Cruz, J., Nunes da Silva, C., Morais de Almeida, S.: The overfull ocnjecture on split-comparability graphs (2017). arXiv:1710.03524v1 [math.CO] (manuscript; 10 Oct 2017)
[10] Bruhn, H., Gellert, L., Lang, R.: Chromatic index, treewidth and maximum degree. Electron. J. Comb. 25, #P2.23 (2018) · Zbl 1391.05102
[11] Cai, J., Ellis, J.A.: NP-completeness of edge-colouring some restricted graphs. Discrete Appl. Math. 30, 15-27 (1991) · Zbl 0797.68078 · doi:10.1016/0166-218X(91)90010-T
[12] Cao, Y., Chen, G.: Lower bound of the average degree of a \[\varDelta\] Δ-critical graph (2018) (Manuscript )
[13] Cao, Y., Chen, G., Jiang, S., Liu, H., Lu, F.: Average degree of edge-chromatic critical graphs (2017). arXiv:1708.01279v1 [math.CO] (Manuscript; 3 Aug 2017) · Zbl 1464.05144
[14] Cao, C., Chen, G., Jiang, S., Liu, H., Lu, F.: Hamiltonicity of edge-chromatic critical graphs (2017). arXiv:1708.08921v1 [math.CO] (manuscript; 29 Aug 2017) · Zbl 1440.05081
[15] Cao, C., Chen, G., Jing, G., Shan, S.: Independence number of edge-chromatic critical graphs (2018). arXiv:1805.05996v1 [math.CO] (manuscript ; 15 May 2018)
[16] Cariolaro, D., Cariolaro, G.: Colouring the petals of a graph. Electron. J. Comb. 10, #R6 (2003) · Zbl 1011.05022
[17] Chen, G., Chen, X., Zhao, Y.: Hamiltonicity of edge chromatic critical graphs. Discrete Math. 340, 3011-3015 (2016) · Zbl 1370.05122 · doi:10.1016/j.disc.2017.07.013
[18] Chen, G., Gao, Y., Kim, R., Postle, L., Shan, S.: Chromatic index determined by fractional chromatic index. J. Comb. Theory Ser. B 131, 85-108 (2018) · Zbl 1387.05083 · doi:10.1016/j.jctb.2018.01.006
[19] Chen, G., Jing, G.: Structural properties of edge-chromatic critical graphs (2017). arXiv:1709.04568v1 [math.CO] (manuscript ; 14 Sep 2017)
[20] Chen, G., Shan, S.: Vizings 2-factor conjecture involving large maximum degree. J. Graph Theory 86, 422-438 (2017) · Zbl 1375.05060 · doi:10.1002/jgt.22135
[21] Chen, G., Yu, X., Zang, W.: Approximating the chromatic index of multigraphs. J. Comb. Optim. 21, 219-246 (2011) · Zbl 1233.90268 · doi:10.1007/s10878-009-9232-y
[22] Chen, X., Zang, W., Zhao, Q.: Densities, matchings, and fractional edge-colorings. SIAM J. Optim. http://hkumath.hku.hk/ imr/IMRPreprintSeries/2018/IMR2018-14.pdf · Zbl 1410.90175
[23] Cheng, J., Lorenzen, K.J., Luo, R., Thompson, J.: A note on the size of edge-chromatic \[44\]-critical graphs. Discrete Math. 339, 2393-2398 (2016) · Zbl 1339.05123 · doi:10.1016/j.disc.2016.04.013
[24] Chetwynd, A.G., Hilton, A.J.W.: Regular graphs of high degree are 1-factorizable. Proc. Lond. Math. Soc. 50, 193-206 (1985) · Zbl 0561.05027 · doi:10.1112/plms/s3-50.2.193
[25] Chetwynd, A.G., Hilton, A.J.W.: Star multigraphs with three vertices of maximum degree. Math. Proc. Camb. Philos. Soc. 100, 303-317 (1986) · doi:10.1017/S030500410006610X
[26] Chetwynd, A.G., Hilton, A.J.W.: 1-Factorizing regular graphs of high degree—an improved bound. Discrete Math. 75, 103-112 (1989) · Zbl 0675.05030 · doi:10.1016/0012-365X(89)90082-4
[27] Chudnovsky, M., Edwards, K., Kawarabayashi, K., Seymour, P.: Edge-colouring seven-regular planar graphs. J. Comb. Theory Ser. B 115, 276-302 (2015) · Zbl 1319.05051 · doi:10.1016/j.jctb.2014.11.005
[28] Chudnovsky, M., Edwards, K., Seymour, P.: Edge-colouring eight-regular planar graphs. J. Comb. Theory Ser. B 115, 303-338 (2015) · Zbl 1319.05052 · doi:10.1016/j.jctb.2015.05.002
[29] Cranston, D.W., Rabern, L.: Subcubic edge chromatic index critcal graphs have many edges. J. Graph Theory 86, 122-136 (2017) · Zbl 1370.05062 · doi:10.1002/jgt.22116
[30] Cranston, D.W., Rabern, L.: Short, : fans and the \[5/65/6\] bound for line graphs (2016). arXiv:1610.03924v1 [math.CO] (manuscript; 13 Oct, 2016) · Zbl 1370.05061
[31] Cranston, D.W., Rabern, L.: The Hilton-Zhao conjecture is true for graphs with maximum degree 4 (2017). arXiv:1703.009594v1 [math.CO] (manuscript; 2 Mar 2018) · Zbl 1419.05069
[32] Csaba, B., Kühn, D., Lo, A., Osthus, D., Treglown, A.: Proof of the \[11\]-factorization and Hamilton decomposition conjectures. Mem. Am. Soc. 244, v+164 (2016) · Zbl 1367.05165
[33] Dvořák, Z., Kawarabayashi, K., Král’, D.: Packing six \[T\] T-joins in plane graphs. J. Comb. Theory Ser. B 116, 287-305 (2016) · Zbl 1327.05075 · doi:10.1016/j.jctb.2015.09.002
[34] Edmonds, J.: Maximum matching and a polyhedron with 0-1 vertices. J. Res. Nat. Bur. Stand. Sect. B 69 B, 125-130 (1965) · Zbl 0141.21802 · doi:10.6028/jres.069B.013
[35] Edwards, K.: Optimization and packing of \[T\] T-joins and \[T\] T-cuts in plane graphs. M.Sc. thesis, McGill University (2011)
[36] Edwards, K., Girão, A., van den Heuvel, J., Kang, R.J., Puleo, G.J., Sereni, J.-S.: Extension from precolored sets of edges. Electron. J. Comb. 25, #P3.1 (2018) · Zbl 1393.05115
[37] Edwards, K., Sanders, D.P., Seymour, P., Thomas, R.: Three-edge-colouring doublecross cubic graphs. J. Comb. Theory Ser. B 119, 66-95 (2016) · Zbl 1334.05037 · doi:10.1016/j.jctb.2015.12.006
[38] Erdős, P., Wilson, R.J.: On the chromatic index of almost all graphs. J. Comb. Theory Ser. B 23, 255-257 (1977) · Zbl 0378.05032 · doi:10.1016/0095-8956(77)90039-9
[39] Favrholdt, L.M., Stiebitz, M., Toft, B.: Graph Edge Colouring: Vizing’s Theorem and Goldberg’s Conjecture. Techn. rep, DMF-2006-10-003, IMADA-PP-2006-20, University of Southern Denmark (2006) (preprint) · Zbl 1339.05001
[40] De Figueiredo, C.M.H., Meidanis, J., de Mello, C.P.: Local conditions for edge-colouring. J. Comb. Math. Comb. Comput. 32, 79-91 (2000) · Zbl 0981.05045
[41] Fiorini, S., Wilson, R.J.: Edge-Colourings of Graphs. Research Notes in Mathematics, vol. 16. Pitman, London (1977) · Zbl 0421.05023
[42] Fournier, J.C.: Coloration des arêtes d’un graphe. Cahiers Centre Études Recherche Opér. 15, 311-314 (1973) · Zbl 0273.05109
[43] Girão, A., Kang, R.J.: Precolouring extension of Vizings theorem (2016). arXiv:1611.09002v1 [math.CO] (manuscript; 28 Nov 2016)
[44] Goldberg, M.K.: On multigraphs of almost maximal chromatic class (Russian). Diskret. Anal. 23, 3-7 (1973)
[45] Goldberg, M.K.: Structure of multigraphs with restriction on the chromatic class (Russian). Diskret. Anal. 30, 3-12 (1977)
[46] Goldberg, M.K.: Edge-coloring of multigraphs: recoloring technique. J. Graph Theory 8, 123-137 (1984) · Zbl 0554.05023 · doi:10.1002/jgt.3190080115
[47] Grünewald, S.: Chromatic index critical graphs and multigraphs. Doctoral thesis, Universität Bielefeld, Bielefeld (2000) · Zbl 0947.05030
[48] Guenin, B.: Packing \[T\] T-joins and edge-colouring in planar graphs (2018) (manuscript in preparation)
[49] Gupta., R.G.: Studies in the theory of graphs. Ph.D. thesis, Tata Institute of Fundamental Research, Bombay (1967)
[50] Gupta, R.P.: On the chromatic index and the cover index of a multigraph. In: Donald, A., Eckmann, B. (eds.) Theory and Applications of Graphs, Proceedings, Michigan May 11-15, 1976. Lecture Notes in Mathematics, vol. 642, pp 204-215. Springer, Berlin, Heidelberg (1978)
[51] Harrelson, J., McDonald, J., Puleo, G.J.: List-edge-colouring planar graphs with precoloured edges (2018). arXiv:1709.04027v3 [math.CO] (manuscript; 9 Jul 2018) · Zbl 1400.05084
[52] Haxell, P., Kierstaed, H.A.: Edge coloring multigraphs without small dense subsets. Discrete Math. 338, 2502-2506 (2015) · Zbl 1318.05028 · doi:10.1016/j.disc.2015.06.022
[53] Haxell, P., Krivelevich, M., Kronenberg, G.: Goldberg’s conjecture is true for random multigraphs (2018). arXiv:1803.00908v1 [math.CO] (manuscript; 2 Mar 2018) · Zbl 1415.05165
[54] Haxell, P., McDonald, J.: On characterizing Vizing’s edge-colouring bound. J. Graph Theory 69, 160-168 (2012) · Zbl 1242.05096 · doi:10.1002/jgt.20571
[55] Heawood, P.J.: Map colour theorem. Q. J. Pure Appl. Math. 24, 332-338 (1890) · JFM 22.0562.02
[56] Hilton, A.J.W., Zhao, C.: On the edge-colouring of graphs whose core has maximum degree two. J. Comb. Math. Comb. Comput. 21, 97-108 (1996) · Zbl 0865.05041
[57] Hochbaum, D.S., Nishizeki, T., Shmoys, D.B.: A better than “best possible” algorithm to edge color multigraphs. J. Algorithms 7, 79-104 (1986) · Zbl 0594.68041 · doi:10.1016/0196-6774(86)90039-8
[58] Holyer, I.: The NP-completeness of edge-colouring. SIAM J. Comput. 10, 718-720 (1981) · Zbl 0473.68034 · doi:10.1137/0210055
[59] Huang, D., Wang, W.: Planar graphs of maximum degree six without seven cycles are class one. Electr. J. Comb. 19, #17 (2012) · Zbl 1252.05063
[60] Jakobsen, I.T.: On critical graphs with chromatic index 4. Discrete Math. 9, 265-276 (1974) · Zbl 0298.05121 · doi:10.1016/0012-365X(74)90009-0
[61] Jakobsen, I.T.: On critical graphs with respect to edge-coloring. In: Hajnal, A., Rado, R., Sós, V. (eds.) Infinite and Finite Sets, Colloq., Keszthely, 1973 (dedicated to P. Erdős on his 60th birthday), vol. II, Colloq. Math. Soc. János Bolyai, vol. 10, pp. 927-934. North-Holland, Amsterdam (1975)
[62] Jin, J., Xu, B.: Edge coloring of \[11\]-planar graphs without intersecting triangles and chordal \[55\]-cycles. ARS Comb. 135, 71-81 (2017) · Zbl 1463.05170
[63] Jin, L., Kang, Y., Steffen, E.: Remarks on planar edge-chromatic critcal graphs. Discrete Appl. Math. 200, 200-202 (2016) · Zbl 1329.05110 · doi:10.1016/j.dam.2015.07.007
[64] Kahn, J.: Asymptotics of the chromatic index for multigraphs. J. Comb. Theory Ser. B 68, 233-254 (1996) · Zbl 0861.05026 · doi:10.1006/jctb.1996.0067
[65] Kanno, J., Shan, S.: Vizing’s 2-factor conjecture involving toughness and maximum degree (2017). arXiv:1709.02241v1 [math.CO] (manuscript; 5 Sep 2017) · Zbl 1412.05045
[66] Kierstead, H.A.: On the chromatic index of multigraphs without large triangles. J. Comb. Theory Ser. B 36, 156-160 (1984) · Zbl 0541.05027 · doi:10.1016/0095-8956(84)90022-4
[67] König, D.: Über Graphen und ihre Anwendungen auf Determinantentheorie und Mengenlehre. Math. Ann. 77, 453-465 (1916) · JFM 46.0146.03 · doi:10.1007/BF01456961
[68] Kostochka, A.: A new tool for proving Vizing’s theorem. Discrete Math. 326, 1-3 (2014) · Zbl 1288.05092 · doi:10.1016/j.disc.2014.02.021
[69] Li, X., Wei, B.: Lower bounds on the number of edges in edge-chromatic critcal graphs with fixed maximum degrees. Discrete Math. 334, 1-12 (2014) · Zbl 1298.05126 · doi:10.1016/j.disc.2014.06.017
[70] Luo, R., Miao, Z., Zhao, Y.: Hamiltonian cycles in critcal graphs with large maximum degree. Graphs Comb. 32, 2019-2028 (2016) · Zbl 1351.05085 · doi:10.1007/s00373-016-1698-7
[71] Luo, R., Zhao, Y.: A sufficient condition for edge chromatic critcal graphs to be Hamiltonian—an approach to Vizing’s \[22\]-factor conjecture. J. Graph Theory 73, 469-482 (2013) · Zbl 1269.05038 · doi:10.1002/jgt.21689
[72] Machado, R.C.S., de Figueiredo, C.M.H.: Decompositions for edge-coloring join graphs and cobipartite graphs. Discrete Appl. Math. 158, 1336-1342 (2010) · Zbl 1218.05050 · doi:10.1016/j.dam.2009.01.009
[73] Machado, R.C.S., de Figueiredo, C.M.H., Trotignon, N.: Edge-colouring and total colouring chordless graphs. Discrete Math. 313, 1547-1552 (2013) · Zbl 1408.05063 · doi:10.1016/j.disc.2013.03.020
[74] Marcotte, O.: Optimal edge-colorings for a class of planar multigraphs. Combinatorica 21, 361-394 (2001) · Zbl 0981.05039 · doi:10.1007/s004930100002
[75] Marcotte, O., Seymour, P.: Extending an edge-coloring. J. Graph Theory 14, 565-573 (2001) · Zbl 0705.05031 · doi:10.1002/jgt.3190140508
[76] McDonald, J.: On a theorem of Goldberg. J. Graph Theory 68, 8-21 (2011) · Zbl 1230.05131 · doi:10.1002/jgt.20537
[77] McDonald, J.; Beineke, LW (ed.); Wilson, RJ (ed.), Edge-colourings (2015), Cambridge
[78] McDonald, J.M., Puleo, G.J.: \[t\] t-cores for \[\varDelta +t\] Δ+t-edge-coloring (2017). arXiv:1710.089824v1 [math.CO] (manuscript; 24 Oct 2017)
[79] Miao, L., Pang, S.: On the size of edge-coloring critical graphs with maximum degree \[44\]. Discrete Math. 308, 5856-5859 (2008) · Zbl 1223.05080 · doi:10.1016/j.disc.2007.10.013
[80] Miao, L., Qu, J., Sun, Q.: On the average degree of critcal graphs with maximum degree six. Discrete Math. 311, 2574-2576 (2011) · Zbl 1238.05147 · doi:10.1016/j.disc.2011.06.029
[81] Morais de Almeida, S., Picinin de Mello, C., Morgana, A.: On the classification problem for split graphs. J. Braz. Comput. Soc. 18, 95-101 (2012) · Zbl 1349.05137 · doi:10.1007/s13173-011-0046-2
[82] Ni, W.-P., Wu, J.-L.: Edge coloring of planar graphs which any two short cycles are adjacent at most once. Theor. Comput. Sci. 516, 133-138 (2014) · Zbl 1278.05084
[83] Ni, W.-P., Wu, J.-L.: Edge coloring of planar graphs which any two short cycles are adjacent at most once. Theor. Comput. Sci. 516, 133-138 (2014) · Zbl 1278.05084 · doi:10.1016/j.tcs.2013.11.011
[84] Nishizeki, T., Kashiwagi, K.: On the 1.1-edge-coloring of multigraphs. SIAM J. Discrete Math. 3, 391-410 (1990) · Zbl 0702.05036 · doi:10.1137/0403035
[85] Ozeki, K.: Kempe equivalence classes of cubic graphs (2017) (Manuscript)
[86] Pang, S., Miao, L., Song, W., Miao, Z.: On the independence number of edge chromatic critical graphs. Discuss. Math. Graph Theory 34, 577-584 (2014) · Zbl 1295.05179 · doi:10.7151/dmgt.1753
[87] Perković, L., Reed, B.: Edge coloring regular graphs of high degree. Discrete Math. 165(166), 567-578 (1997) · Zbl 0902.05030 · doi:10.1016/S0012-365X(96)00202-6
[88] Plantholt, M.: A combined logarithmic bound on the chromatic index of multigraphs. J. Graph Theory 73, 239-259 (2013) · Zbl 1269.05040 · doi:10.1002/jgt.21670
[89] Plantholt, M., Tipnis, S.K.: All regular multigraphs of even order and high degree are 1-factorable. Electron. J. Comb. 8, #R41 (2001) · Zbl 0981.05079
[90] Puleo, G.J.: Maximal \[k\] k-edge-colorable subgraphs, Vizing’s theorem, and Tuza’s conjecture (2017). arXiv:1510.07017v4 [math.CO] (manuscript; 6 Mar 2017) · Zbl 1361.05053
[91] Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Semin. Univ. Hambg 29, 107-117 (1965) · Zbl 0132.20701 · doi:10.1007/BF02996313
[92] Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: The four colour theorem. J. Comb. Theory Ser. B 70, 2-44 (1997) · Zbl 0883.05056 · doi:10.1006/jctb.1997.1750
[93] Robertson, N., Seymour, P., Thomas, R.: Tutte’s edge-colouring conjecture. J. Comb. Theory Ser. B 70, 166-183 (1997) · Zbl 0883.05055 · doi:10.1006/jctb.1997.1752
[94] Robertson, N., Seymour, P., Thomas, R.: Excluded minors in cubic graphs (2014). arXiv:1402.2118v1 [math.CO] (manuscript; 9 Mar 2014) · Zbl 1415.05169
[95] Sanders, P., Steurer, D.: An asymptotic approximation scheme for multigraph edge coloring. ACM Trans. Algorithms 4, 21 (2008) · Zbl 1445.68176
[96] Sanders, D., Thomas, R.: Edge three-cubic apex graphs (2018) (manuscript in preparation)
[97] Sanders, D., Zhao, Y.: Planar graphs of maximum degree seven are class I. J. Comb. Theory Ser. B 83, 201-212 (2001) · Zbl 1024.05031 · doi:10.1006/jctb.2001.2047
[98] Scheide, D.: Edge Colourings of Multigraphs. Doctoral thesis., TU Ilmenau, Ilmenau (2008)
[99] Scheide, D.: Graph edge colouring: Tashkinov trees and Goldberg’s conjecture. J. Comb. Theory Ser. B 100, 68-96 (2010) · Zbl 1210.05051 · doi:10.1016/j.jctb.2009.04.001
[100] Scheide, D., Stiebitz, M.: On Vizing’s bound for the chromatic index of a multigraph. Discrete Math. 309, 4920-4925 (2009) · Zbl 1216.05038 · doi:10.1016/j.disc.2008.04.046
[101] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003) · Zbl 1041.90001
[102] Seymour, P.: On multicolorings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. Lond. Math. Soc. 38, 423-460 (1979) · Zbl 0411.05037 · doi:10.1112/plms/s3-38.3.423
[103] Seymour, P.: On Tutte’s extension of the four-color problem. J. Comb. Theory Ser. B 31, 82-94 (1981) · Zbl 0471.05031 · doi:10.1016/S0095-8956(81)80013-5
[104] Seymour, P.: Colouring series-parallel graphs. Combinatorica 10, 379-392 (1990) · Zbl 0721.05023 · doi:10.1007/BF02128672
[105] Shannon, C.E.: A theorem on coloring the lines of a network. J. Math. Phys. 28, 148-151 (1949) · Zbl 0032.43203 · doi:10.1002/sapm1949281148
[106] De Simone, C., Galluccio, A.: Edge-colouring of joins of regular graphs II. J. Comb. Optim. 25, 78-90 (2013) · Zbl 1273.05064 · doi:10.1007/s10878-011-9420-4
[107] Steffen, E.: Approximating Vizing’s independence number conjecture. Aust. J. Comb. 71, 153-160 (2018) · Zbl 1404.05160
[108] Stiebitz, M., Scheide, D., Toft, B., Favrholdt, L.: Graph Edge Coloring: Vizing’s Theorem and Goldberg’s Conjecture. Wiley, New York (2012) · Zbl 1339.05001
[109] Tait, P.G.: On the colouring of maps. Proc. R. Soc. Edinb. Sect. A 10, 501-503, 729 (1978-1980) · JFM 12.0408.02
[110] Tashkinov, V.A.: On an algorithm for the edge coloring of multigraphs (Russian). Diskretn. Anal. Issled. Oper. Ser. 1(7), 72-85 (2000) · Zbl 0955.05036
[111] Tutte, W.: On the algebraic theory of graph colorings. J. Comb. Theory Ser. B 23, 15-50 (1966) · Zbl 0139.41402 · doi:10.1016/S0021-9800(66)80004-2
[112] Tuza, Z.: A conjecture on triangles of graphs. Graphs Comb. 6, 373-380 (1990) · Zbl 0724.05059 · doi:10.1007/BF01787705
[113] Vaughan, E.R.: An asymptotic version of the multigraph \[11\]-factorization conjecture. J. Graph Theory 72, 19-29 (2013) · Zbl 1259.05141 · doi:10.1002/jgt.21629
[114] Vizing, V.G.:. On an estimate of the chromatic class of a \[p\] p-graph (Russian). Diskret. Anal.3, 25-30 (1964) [English translation in (108, App. A1)]
[115] Vizing, V.G.: The chromatic class of a multigraph (Russian). Kibernetika (Kiev) 3, 29-39 (1965) [English translation in: Cybernetics and System Analysis 1, 32-41 (1965)]
[116] Vizing, V.G.: Critical graphs with a given chromatic class (Russian). Diskret. Anal. 5, 9-17 (1965) [English translation in (108, App. A1)]
[117] Vizing, V.G.: Some unsolved problems in graph theory (Russian). Uspekhi Mat. Nauk 23, 117-134 (1968) [English translation in: Russian Mathematical Surveys 23, 125-141 (1968)] · Zbl 0192.60502
[118] Wang, Y.: Edge coloring of graphs embedded in a surface of negative characteristic. Acta Math. Appl. Sin. Engl. Ser. 33, 709-716 (2017) · Zbl 1390.05076 · doi:10.1007/s10255-017-0693-y
[119] Wang, Y., Xu, L.: A sufficient condition for a plane graph with maximum degree 6 to be class \[11\]. Discrete Appl. Math. 161, 307-310 (2013) · Zbl 1254.05060 · doi:10.1016/j.dam.2012.08.011
[120] Woodall, D.R.: The average degree of an edge-chromatic critical graph II. J. Graph Theory 56, 194-218 (2007) · Zbl 1137.05037 · doi:10.1002/jgt.20259
[121] Woodall, D.R.: The independence number of an edge-chromatic critical graph. J. Graph Theory 66, 98-103 (2011) · Zbl 1216.05040 · doi:10.1002/jgt.20493
[122] Woodall, D.R.: Edge-chromatic 3-critical graphs have more edges (2018) (Manuscript)
[123] Wu, J.-L., Xue, L.: Edge colorings of planar graphs without \[55\]-cycles with two chords. Theor. Comput. Sci. 518, 124-127 (2014) · Zbl 1370.05075 · doi:10.1016/j.tcs.2013.07.027
[124] Zhang, L.: Every planar graph with maximum degree 7 is class I. Graphs Comb. 16, 467-495 (2000) · Zbl 0988.05042 · doi:10.1007/s003730070009
[125] Zhang, W., Wu, J.-L.: Some sufficient conditions for \[11\]-planar graphs to be class \[11\]. Theor. Comput. Sci. 566, 50-58 (2015) · Zbl 1318.05020 · doi:10.1016/j.tcs.2014.11.031
[126] Zhang, W., Wu, J.-L.: Edge coloring of planar graph without adjacent \[77\]-cycles. Theor. Comput. Sci. 739, 59-64 (2018) · Zbl 1394.05038 · doi:10.1016/j.tcs.2018.05.006
[127] Zhang, X.: The edge chromatic number of outer-\[11\]-planar graphs. Discrete Math. 339, 1393-1399 (2016) · Zbl 1329.05122 · doi:10.1016/j.disc.2015.12.009
[128] Zhang, X., Liu, G.: On edge colorings \[11\]-planar graphs without adjacent triangles. Inf. Process. Lett. 112, 138-142 (2012) · Zbl 1239.05078 · doi:10.1016/j.ipl.2011.10.021
[129] Zhang, X., Liu, G.: On edge colorings \[11\]-planar graphs without chordal \[55\]-cycles. ARS Comb. 104, 431-436 (2012) · Zbl 1274.05186
[130] Zhang, X., Wu, J.-L.: On edge colorings \[11\]-planar graphs. Inf. Process. Lett. 111, 124-128 (2011) · Zbl 1259.05050 · doi:10.1016/j.ipl.2010.11.001
[131] Zorzi, A., Zatesko, L.M.: On the chromatic index of join graphs and triangle-free graphs with large maximum degree. Discrete Appl. Math. 245, 183-189 (2018) · Zbl 1387.05101 · doi:10.1016/j.dam.2016.10.022
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.