Path choosability of planar graphs (Q1627209)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Path choosability of planar graphs |
scientific article |
Statements
Path choosability of planar graphs (English)
0 references
22 November 2018
0 references
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.
0 references
graph coloring
0 references
list coloring
0 references
choosability
0 references
path coloring
0 references
0 references