×

zbMATH — the first resource for mathematics

On edge colorings of 1-planar graphs without adjacent triangles. (English) Zbl 1239.05078
Summary: A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-planar graph without adjacent triangles and with maximum degree \(\Delta \geqslant 8\) can be edge-colored with \(\Delta \) colors.

MSC:
05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bu, Y.; Wang, W., Some sufficient conditions for a planar graph of maximum degree six to be class 1, Discrete math., 306, 1440-1445, (2006) · Zbl 1095.05014
[2] Fabrici, I.; Madaras, T., The structure of 1-planar graphs, Discrete math., 307, 854-865, (2007) · Zbl 1111.05026
[3] 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
[4] Ringel, G., Ein sechsfarbenproblem auf der kugel, Abh. math. semin. univ. hambg., 29, 107-117, (1965) · Zbl 0132.20701
[5] 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
[6] Vizing, V.G., Critical graphs with given chromatic class, Diskret. analiz., 5, 9-17, (1965)
[7] Vizing, V.G., Some unsolved problems in graph theory, Uspekhi mat. nauk, Russian math. surveys, 23, 125-141, (1968), (in Russian); English transl. in: · Zbl 0192.60502
[8] West, D.B., Introduction to graph theory, (2001), Pearson Education, Inc.
[9] Zhang, L., Every planar graph with maximum degree 7 is of class 1, Graphs combin., 16, 467-495, (2000) · Zbl 0988.05042
[10] Zhang, X., Class two 1-planar graphs with maximum degree six or seven
[11] Zhang, X.; Wu, J.-L., On edge colorings of 1-planar graphs, Inform. process. lett., 111, 3, 124-128, (2011) · Zbl 1259.05050
[12] X. Zhang, G. Liu, On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Combinatoria 104 (2012), in press. · Zbl 1274.05186
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.