A structural theorem for planar graphs with some applications |
| |
Authors: | Huiyu ShengYingqian Wang |
| |
Affiliation: | College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua, 321004, China |
| |
Abstract: | In this note, we prove a structural theorem for planar graphs, namely that every planar graph has one of four possible configurations: (1) a vertex of degree 1, (2) intersecting triangles, (3) an edge xy with d(x)+d(y)≤9, (4) a 2-alternating cycle. Applying this theorem, new moderate results on edge choosability, total choosability, edge-partitions and linear arboricity of planar graphs are obtained. |
| |
Keywords: | Planar graph Intersecting triangles List edge-coloring List total coloring Edge-partition Linear 2-arboricity |
本文献已被 ScienceDirect 等数据库收录! |
|