On list-coloring extendable outerplanar graphs

Joan P. Hutchinson

Abstract


We investigate a variation on Thomassen's 2- and 3-extendability of precoloring extensions for list-coloring graphs. For an outerplanar graph G with i, j ≤ 2, we say that G is {i, j}-extendable if for every pair of nonadjacent vertices x and y, whenever x is assigned an i-list, y is assigned a j-list, and all other vertices have a 3-list, G is list-colorable. We characterize the {1, 1}- and the {1, 2}-extendable outerplanar graphs and prove that every outerplanar graph is {2, 2}-extendable.

Keywords


Graph List-Coloring, Coloring Extendability, Outerplanar Graphs

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.179.189

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications