Article ID Journal Published Year Pages File Type
428709 Information Processing Letters 2009 4 Pages PDF
Abstract

A graph G is edge-L-colorable, if for a given edge assignment , there exits a proper edge-coloring ϕ of G such that ϕ(e)∈L(e) for all e∈E(G). If G is edge-L-colorable for every edge assignment L with |L(e)|⩾k for e∈E(G), then G is said to be edge-k-choosable. In this paper, we prove that if G is a planar graph without non-induced 5-cycles, then G is edge-k-choosable, where k=max{7,Δ(G)+1}.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics