Path choosability of planar graphs
type: Item
instance of: scholarly article
title: Path choosability of planar graphs
zbMATH Open document ID: 1440.05082
author: Glenn G. Chappell
author: Chris Hartman
published in: The Electronic Journal of Combinatorics
publication date: 2018-11-22T00:00:00Z
full work available at URL: v25i4p33
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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6983031
zbMATH Keywords: graph coloring
zbMATH Keywords: list coloring
zbMATH Keywords: choosability
zbMATH Keywords: path coloring
MaRDI profile type: Publication
cites work: Path chromatic numbers of graphs
cites work: Q3142409
cites work: The smallest n-uniform hypergraph with positive discrepancy
cites work: Choosability and fractional chromatic numbers
cites work: Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths
cites work: List strong linear 2-arboricity of sparse graphs
cites work: Q3688407
cites work: Q3424891
cites work: The Point-Arboricity of Planar Graphs
cites work: Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
cites work: Q4230860
cites work: Q3922703
cites work: Acyclic colorings of planar graphs
cites work: Some results on \((a:b)\)-choosability
cites work: Improper choosability of graphs and maximum average degree
cites work: Q4263476
cites work: Q4518396
cites work: On the linear vertex-arboricity of a planar graph
cites work: List Improper Colourings of Planar Graphs
cites work: List improper colorings of planar graphs with prescribed girth
cites work: Graph colorings with local constraints -- a survey
cites work: Q4888118
cites work: Q4492757
cites work: Defective and clustered graph colouring
cites work: Defective choosability of graphs in surfaces
Recommended article: Choosability of planar graphs
Recommended article: Q3129827
Recommended article: The complexity of planar graph choosability
Recommended article: Minimum choosability of planar graphs
Recommended article: On the path separability of planar graphs
Recommended article: The entire choosability of plane graphs
Recommended article: Choosability in signed planar graphs
Recommended article: On the Path-Width of Planar Graphs
Recommended article: Q3922703
Recommended article: On the total choosability of planar graphs and of sparse graphs
description: scientific article; zbMATH DE number 6983031