Equitable Coloring of Three Classes of 1-planar Graphs  

作　　者：Xin ZHANG Hui-juan WANG Lan XU 

机构地区：[1]School of Mathematics and Statistics, Xidian University, Xi'an 710071, China [2]College of Mathematics, Qingdao University, Qingdao 266071, China [3]Department of Mathematics, Changji University, Changji 831100, China

出　　处：《Acta Mathematicae Applicatae Sinica》2018年第2期362-372,共11页应用数学学报（英文版）

基　　金：supported by the Natural Science Basic Research Plan in Shaanxi Province of China(No.2017JM1010);the Fundamental Research Funds for the Central Universities(No.JB170706);the Specialized Research Fund for the Doctoral Program of Higher Education(No.20130203120021);the National Natural Science Foundation of China(No.11301410);the National Natural Science Foundation of China(No.11501316);the Shandong Provincial Natural Science Foundation,China(No.ZR2014AQ001);the China Postdoctoral Science Foundation(No.2015M570569);supported by the Natural Science Foundation of Xinjiang Province of China(No.2015211A003)

摘　　要：A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree A at least 15, 13 or 12 has an equitable △-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree A at least 15, 13 or 12 has an equitable △-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.

关 键 词：1-planar graph equitable coloring independent crossing 

分 类 号：O157.5[理学—数学]