Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420263 | Discrete Applied Mathematics | 2011 | 5 Pages |
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 xyxy with d(x)+d(y)≤9d(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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Huiyu Sheng, Yingqian Wang,