Path choosability of planar graphs

Glenn G. Chappell¹ ; Chris Hartman¹

¹University of Alaska

The electronic journal of combinatorics, Tome 25 (2018) no. 4

Résumé

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.

Détail

DOI : 10.37236/7139

Classification : 05C15, 05C10, 05C38
Mots-clés : graph coloring, list coloring, choosability, path coloring