Path choosability of planar graphs (Q1627209)

Summary: 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 \geq 2\). For planar graphs we conjecture that a similar result holds with \(q/r \geq 3\); we present partial results toward this conjecture.