Path choosability of planar graphs

MaRDI QIDQ1627209zbMATH OpenFDO

Authors Glenn G. Chappell, Chris Hartman

Publication date 22 November 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p33

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

choosability graph coloring list coloring path coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Review text

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Path choosability of planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1627209)