Akempic triangulations with 4 odd vertices (Q1062068)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Akempic triangulations with 4 odd vertices
scientific article

    Statements

    Akempic triangulations with 4 odd vertices (English)
    0 references
    0 references
    1985
    0 references
    A triangulation of the plane is akempic if it has a 4-colouring C where any two adjacent triangles have the four vertices of the two triangles coloured with all four colours, and C cannot be changed to an essentially different 4-colouring by a Kempe interchange (i.e. the vertices of any two of the four colours span a connected subgraph). \textit{S. Fisk} [Adv. Math. 24, 298-340 (1977; Zbl 0358.05023)] proved that there are two families of akempic triangulations with exactly four vertices of degree 3 and all other vertices of degree 6, and he asked if there are more such graphs. This question is here answered in the affirmative, based on a characterization of duals of akempic triangulations using voltage graphs. In particular it is proved that the number of non-isomorphic such triangulations on 4n vertices tends to infinity with n. It is announced that an exact formula for their number will appear elsewhere.
    0 references
    graph coloring
    0 references
    Kempe interchange
    0 references
    triangulations
    0 references
    0 references

    Identifiers