pith. machine review for the scientific record. sign in

arxiv: 1209.0366 · v2 · submitted 2012-09-03 · 🧮 math.CO · cs.DM

Recognition: unknown

5-list-coloring planar graphs with distant precolored vertices

Authors on Pith no claims yet
classification 🧮 math.CO cs.DM
keywords verticesplanarcontainseverygraphgraphsl-colorableprecolored
0
0 comments X
read the original abstract

We answer positively the question of Albertson asking whether every planar graph can be $5$-list-colored even if it contains precolored vertices, as long as they are sufficiently far apart from each other. In order to prove this claim, we also give bounds on the sizes of graphs critical with respect to 5-list coloring. In particular, if G is a planar graph, H is a connected subgraph of G and L is an assignment of lists of colors to the vertices of G such that |L(v)| >= 5 for every v in V(G)-V(H) and G is not L-colorable, then G contains a subgraph with O(|H|^2) vertices that is not L-colorable.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.