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...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.展开更多
基金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.
