Pith. sign in

REVIEW

An update on reconfiguring $10$-colorings of planar graphs

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 2002.05383 v1 pith:YQEVUVUM submitted 2020-02-13 math.CO

classification math.CO
keywords coloringsgraphplanardiametergraphsvertexverticesadjacent
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

The reconfiguration graph $R_k(G)$ for the $k$-colorings of a graph $G$ has as vertex set the set of all possible proper $k$-colorings of $G$ and two colorings are adjacent if they differ in the color of exactly one vertex. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that if $G$ is a planar graph with $n$ vertices, then $R_{12}(G)$ has diameter at most $6n$. We improve on the number of colors, showing that $R_{10}(G)$ has diameter at most $8n$ for every planar graph $G$ with $n$ vertices.

Discussion (0). Continue with ORCID to comment.

Pith tools