Pith. sign in

REVIEW

5-list-coloring planar graphs with distant precolored vertices

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1209.0366 v2 pith:IR6KPFUB submitted 2012-09-03 math.CO cs.DM

classification math.COcs.DM
keywords verticesplanarcontainseverygraphgraphsl-colorableprecolored
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Pith tools