Linear Arboricity of NIC-Planar Graphs  

作　　者：Bei NIU Xin ZHANG 

机构地区：[1]School of Mathematics and Statistics, Xidian University

出　　处：《Acta Mathematicae Applicatae Sinica》2019年第4期924-934,共11页应用数学学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China(Nos.11871055,11301410);the Natural Science Basic Research Plan in Shaanxi Province of China(No.2017JM1010);the Fundamental Research Funds for the Central Universities(Nos.JB170706)

摘　　要：A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end vertex. It is proved that every NIC-planar graph with minimum degree at least 2(resp. 3) contains either an edge with degree sum at most 23(resp. 17) or a 2-alternating cycle(resp. 3-alternating quadrilateral). By applying those structural theorems, we confirm the Linear Arboricity Conjecture for NIC-planar graphs with maximum degree at least 14 and determine the linear arboricity of NIC-planar graphs with maximum degree at least 21.A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end vertex. It is proved that every NIC-planar graph with minimum degree at least 2(resp. 3) contains either an edge with degree sum at most 23(resp. 17) or a 2-alternating cycle(resp. 3-alternating quadrilateral). By applying those structural theorems, we confirm the Linear Arboricity Conjecture for NIC-planar graphs with maximum degree at least 14 and determine the linear arboricity of NIC-planar graphs with maximum degree at least 21.

关 键 词：NIC-planar GRAPH LINEAR ARBORICITY LIGHT EDGE 

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