Path Choosability of Planar Graphs - Chappell, Glenn G.; Hartman, Chris (The Electronic Journal of Combinatorics, 2018)
A path coloring of a graph G is a vertex coloring of G such that each color class induces a disjoint union of paths. We consider a path-coloring version of list coloring for planar and outerplanar graphs. We show that if each vertex of a planar graph is assigned a list of 3 colors, then the graph admits a path coloring in which each vertex receives a color from its list. We prove a similar result for outerplanar graphs and lists of size 2. For outerplanar graphs we prove a multicoloring generalization. We assign each vertex of a graph a list of q colors. We wish to color each vertex with r colors from its list so that, for each color, the set of vertices receiving it induces a disjoint union of paths. We show that we can do this for all outerplanar graphs if and only if q/r 2. For planar graphs we conjecture that a similar result holds with q/r 3; we present partial results toward this conjecture.