• Title of article

    List precoloring extension in planar graphs

  • Author/Authors

    Axenovich، نويسنده , , Maria and Hutchinson، نويسنده , , Joan P. and Lastrina، نويسنده , , Michelle A.، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2011
  • Pages
    11
  • From page
    1046
  • To page
    1056
  • Abstract
    A celebrated result of Thomassen states that not only can every planar graph be colored properly with five colors, but no matter how arbitrary palettes of five colors are assigned to vertices, one can choose a color from the corresponding palette for each vertex so that the resulting coloring is proper. This result is referred to as 5-choosability of planar graphs. Albertson asked whether Thomassen’s theorem can be extended by precoloring some vertices which are at a large enough distance apart in a graph. Here, among others, we answer the question in the case when the graph does not contain short cycles separating precolored vertices and when there is a “wide” Steiner tree containing all the precolored vertices.
  • Keywords
    Coloring extension , list-coloring , Albertson’s conjecture , Planar graphs
  • Journal title
    Discrete Mathematics
  • Serial Year
    2011
  • Journal title
    Discrete Mathematics
  • Record number

    1599614