The structure of plane graphs with independent crossings and its applications to coloring problems |
| |
Authors: | Xin Zhang Guizhen Liu |
| |
Institution: | 1. Department of Mathematics, Xidian University, 2 Tai Bai Nan Rd., Xi’an, 710071, China 2. School of Mathematics, Shandong University, 27 Shan Da Nan Rd., Jinan, 250100, China
|
| |
Abstract: | If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is ?Δ/2? if Δ ≥ 17, where G is an IC-planar graph and Δ is the maximum degree of G. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|