• 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