Path Choosability of Planar Graphs

Abstract

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