×

On edge colorings of 1-toroidal graphs. (English) Zbl 1268.05053

Summary: A graph is 1-toroidal, if it can be embedded in the torus so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-toroidal graph with maximum degree \(\Delta\geq 10\) is of class one in terms of edge coloring. Meanwhile, we show that there exist class two 1-toroidal graphs with maximum degree \(\Delta\) for each \(\Delta\leq 8\).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, North-Holland, New York, 1976 · Zbl 1226.05083
[2] Sanders, D. P., Zhao, Y.: Planar graphs of maximum degree seven are class I. J. Combin. Theory Ser. B, 83, 201–212 (2001) · Zbl 1024.05031 · doi:10.1006/jctb.2001.2047
[3] Zhang, L.: Every planar graph with maximum degree 7 is of class 1. Graphs Combin., 16, 467–495 (2000) · Zbl 0988.05042 · doi:10.1007/s003730070009
[4] Vizing, V. G.: Critical graphs with given chromatic class. Diskret. Analiz., 5, 9–17 (1965)
[5] Ringel, G.: Ein Sechsfarbenproblem auf der Kugel (in German). Abh. Math. Semin. Univ. Hambg., 29, 107–117 (1965) · Zbl 0132.20701 · doi:10.1007/BF02996313
[6] Borodin, O. V.: Solution of Ringel’s problems on the vertex-face coloring of plane graphs and on the coloring of 1-planar graphs. Diskret. Analiz., 41, 12–26 (1984) · Zbl 0565.05027
[7] Borodin, O. V.: A new proof of the 6-color theorem. J. Graph Theory, 19(4), 507–521 (1995) · Zbl 0826.05027 · doi:10.1002/jgt.3190190406
[8] Borodin, O. V., Dmitriev, I. G., Ivanova, A. O.: The height of a cycle of length 4 in 1-planar graphs with minimum degree 5 without triangles (in Russian). Diskretn. Anal. Issled. Oper., 15(1), 11–16 (2008) · Zbl 1249.05203
[9] Borodin, O. V., Kostochka, A. V., Raspaud, A., et al.: Acyclic colouring of 1-planar graphs. Discrete Appl. Math., 114, 29–41 (2001) · Zbl 0996.05053 · doi:10.1016/S0166-218X(00)00359-0
[10] Chen, Z.-Z., Kouno, M.: A linear-time algorithm for 7-coloring 1-plane graphs. Algorithmica, 43(3), 147–177 (2005) · Zbl 1082.05084 · doi:10.1007/s00453-004-1134-x
[11] Fabrici, I., Madaras, T.: The structure of 1-planar graphs. Discrete Math., 307, 854–865 (2007) · Zbl 1111.05026 · doi:10.1016/j.disc.2005.11.056
[12] Hudák, D., Madaras, T.: On local structures of 1-planar graphs of minimum degree 5 and girth 4. Discuss. Math. Graph Theory, 29, 385–400 (2009) · Zbl 1194.05025 · doi:10.7151/dmgt.1454
[13] Hudák, D., Madaras, T.: On local properties of 1-planar graphs with high minimum degree. Ars Math. Contemp., 4(2), 245–254 (2011) · Zbl 1237.05053
[14] Hudák, D., Šugerek P.: Light edges in 1-planar graphs with prescribed minimum degree. Discuss. Math. Graph Theory, 32(3), 545–556 (2012) · Zbl 1262.05032 · doi:10.7151/dmgt.1625
[15] Zhang, X., Liu, G.: On edge colorings of 1-planar graphs without adjacent triangles. Inform. Process. Lett., 112, 138–142 (2012) · Zbl 1239.05078 · doi:10.1016/j.ipl.2011.10.021
[16] Zhang, X., Liu, G.: On edge colorings of 1-planar graphs without chordal 5-cycles. Ars Combin., 104, 431–436 (2012) · Zbl 1274.05186
[17] Zhang, X., Liu, G., Wu, J.-L.: Edge coloring of triangle-free 1-planar graphs (in Chinese). J. Shandong Univ. Nat. Sci., 45(6), 15–17 (2010) · Zbl 1240.05125
[18] Zhang, X., Liu, G., Wu, J.-L.: (1, {\(\lambda\)})-embedded graphs and the acyclic edge choosability. Bull. Korean Math. Soc., 49(3), 573–580 (2012) · Zbl 1242.05186 · doi:10.4134/BKMS.2012.49.3.573
[19] Zhang, X., Wu, J.-L.: On edge colorings of 1-planar graphs. Inform. Process. Lett., 111(3), 124–128 (2011) · Zbl 1259.05050 · doi:10.1016/j.ipl.2010.11.001
[20] Zhang, X., Liu, G., Wu, J.-L.: On the linear arboricity of 1-planar graphs. OR Trans., 15(3), 38–44 (2011) · Zbl 1249.05085
[21] Zhang, X., Liu, G., Wu, J.-L.: Light subgraphs in the family of 1-planar graphs with high minimum degree. Acta Mathematica Sinica, English series, 28(6), 1155–1168 (2012) · Zbl 1252.05047 · doi:10.1007/s10114-011-0439-3
[22] Zhang, X., Wu, J.-L., Liu, G.: New upper bounds for the heights of some light subgraphs in 1-planar graphs with high minimum degree. Discrete Math. Theor. Comput. Sci., 13(3), 9–16 (2011) · Zbl 1283.05075
[23] Zhang, X., Wu, J.-L., Liu, G.: List edge and list total coloring of 1-planar graphs. Front. Math. China, 7(5), 1005–1018 (2012) · Zbl 1254.05050 · doi:10.1007/s11464-012-0184-7
[24] Zhang, X., Yu, Y., Liu, G.: On (p, 1)-total labelling of 1-planar graphs. Cent. Eur. J. Math., 9(6), 1424–1434 (2011) · Zbl 1227.05135 · doi:10.2478/s11533-011-0092-1
[25] Luo, R., Miao, L., Zhao, Y.: The size of edge chromatic critical graphs with maximum degree 6. J. Graph Theory, 60, 149–171 (2009) · Zbl 1247.05083 · doi:10.1002/jgt.20351
[26] Vizing, V. G.: Some unsolved problems in graph theory (in Russian). Uspekhi Mat. Nauk., 23, 117–134 (1968); English translation in Russian Math. Surveys, 23, 125–141 (1968) · Zbl 0177.52301
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.