Title of article :
Entire choosability of near-outerplane graphs
Author/Authors :
Hetherington، نويسنده , , Timothy J.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
13
From page :
2153
To page :
2165
Abstract :
It is proved that if G is a plane embedding of a K 4 -minor-free graph with maximum degree Δ , then G is entirely 7-choosable if Δ ≤ 4 and G is entirely ( Δ + 2 ) -choosable if Δ ≥ 5 ; that is, if every vertex, edge and face of G is given a list of max { 7 , Δ + 2 } colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if G is a plane embedding of a K 2 , 3 -minor-free graph or a ( K 2 ̄ + ( K 1 ∪ K 2 ) ) -minor-free graph. As a special case this proves that the Entire Coluring Conjecture, that a plane graph is entirely ( Δ + 4 ) -colourable, holds if G is a plane embedding of a K 4 -minor-free graph, a K 2 , 3 -minor-free graph or a ( K 2 ̄ + ( K 1 ∪ K 2 ) ) -minor-free graph.
Keywords :
outerplanar graph , minor-free graph , Series–parallel graph
Journal title :
Discrete Mathematics
Serial Year :
2009
Journal title :
Discrete Mathematics
Record number :
1598684
Link To Document :
بازگشت