Article ID Journal Published Year Pages File Type
4649808 Discrete Mathematics 2009 8 Pages PDF
Abstract

Let GG be a planar graph without 5-cycles or without 6-cycles. In this paper, we prove that if GG is connected and δ(G)≥2δ(G)≥2, then there exists an edge xy∈E(G)xy∈E(G) such that d(x)+d(y)≤9d(x)+d(y)≤9, or there is a 2-alternating cycle. By using the above result, we obtain that (1) its linear 2-arboricity la2(G)≤⌈Δ(G)+12⌉+6, (2) its list total chromatic number is Δ(G)+1Δ(G)+1 if Δ(G)≥8Δ(G)≥8, and (3) its list edge chromatic number is Δ(G)Δ(G) if Δ(G)≥8Δ(G)≥8.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,