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