On list-coloring extendable outerplanar graphs
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
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