Plane Graphs are Facially-non-repetitively 10^{4 \cdot10⁷}-Choosable

DOI10.37236/7129arXiv1706.09685MaRDI QIDQ6288432FDOQ6288432

Authors: Grzegorz Gutowski 

Publication date: 29 June 2017

Abstract: A sequence $left(x_1,x_2,ldots,x_{2n}ight)$ of even length is a repetition if $left(x_1,ldots,x_{n}ight)=left(x_{n+1},ldots,x_{2n}ight)$. We prove existence of a constant $C<10^{4cdot10^7}$ such that given any planar drawing of a graph $G$, and a list $L(v)$ of $C$ permissible colors for each vertex $v$ in $G$, there is a choice of a permissible color for each vertex such that the sequence of colors of the vertices on any facial simple path in $G$ is not a repetition.

This page was built for publication: Plane Graphs are Facially-non-repetitively $10^{4 \cdot10^7}$-Choosable

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