Every plane graph is facially-non-repetitively \(C\)-choosable (Q1753049)

From MaRDI portal





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
    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