Every plane graph is facially-non-repetitively \(C\)-choosable (Q1753049)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Every plane graph is facially-non-repetitively \(C\)-choosable |
scientific article; zbMATH DE number 6873118
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Every plane graph is facially-non-repetitively \(C\)-choosable |
scientific article; zbMATH DE number 6873118 |
Statements
Every plane graph is facially-non-repetitively \(C\)-choosable (English)
0 references
25 May 2018
0 references
Summary: A sequence \((x_1,x_2,\ldots, x_{2n})\) of even length is a repetition if \((x_1,\ldots,x_n) =(x_{n+1},\ldots,x_{2n})\). We prove existence of a constant \(C < 10^{4 \cdot 10^{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.
0 references
planar graphs
0 references
non-repetitive colorings
0 references