On list-coloring extendable outerplanar graphs - Hutchinson, Joan P. (Ars mathematica contemporanea, 2012)
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 \le 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: barvanje grafov; coloring extendability; graph list-coloring; graph theory; outerplanar graphs; seznamsko barvanje; teorija grafov