Sufficient sparseness conditions for G2 G 2 to be (?+1) ( ? + 1 ) -choosable, when ??5 ? ? 5
We determine the list chromatic number of the square of a graph ??(G2) ? ? ( G 2 ) in terms of its maximum degree ? ? when its maximum average degree, denoted mad ( G ) , is sufficiently small. For ??6 ? ? 6 , if mad ( G ) < 2 + 4 ? ? 8 5 ? + 2 , then ??(G2)=?+1 ? ? ( G 2 ) = ? + 1 . In particular, if G G is planar with girth g ? 7 + 12 ? ? 2 , then ??(G2)=?+1 ? ? ( G 2 ) = ? + 1 . Under the same conditions, ? ? i ( G ) = ? , where ? ? i is the list injective chromatic number.
square of a graph maximum degree maximum average degree girth choosability discharging