Article ID Journal Published Year Pages File Type
6872468 Discrete Applied Mathematics 2014 10 Pages PDF
Abstract
We determine the list chromatic number of the square of a graph χℓ(G2) in terms of its maximum degree Δ when its maximum average degree, denoted mad(G), is sufficiently small. For Δ≥6, if mad(G)<2+4Δ−85Δ+2, then χℓ(G2)=Δ+1. In particular, if G is planar with girth g≥7+12Δ−2, then χℓ(G2)=Δ+1. Under the same conditions, χℓi(G)=Δ, where χℓi is the list injective chromatic number.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,