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 the normal view instead:

scientific article; zbMATH DE number 6873118
Language Label Description Also known as
default for all languages
No label defined
    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
      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

      Identifiers