2025/11/01 by Jan Florek, Florek, Jan · 1 citation
Mathematics · Computer Science · #Finite Group Theory Research #Advanced Combinatorial Mathematics #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2511.00485
Let Gn, where n \geqslant 5, be a simple plane triangulation which has 2 non-adjacent vertices of degree n (called poles of Gn) and 2n vertices of degree~5. A set of Kempe equivalent 4-colourings of Gn is called a Kempe class. The number of Kempe classes of Gn is enumerated. In particular it is shown that there is at least \lfloor (n)/(6) \rfloor Kempe classes of Gn. We say that 4-colourings A, B of Gn are equal if there exists a permutation~P of the set of colours such that A = P ∘ B. Otherwise, A, B are different. The number of different 4-colourings of Gn is enumerated. Suppose that Hn = Gn - b, where b is a pole of Gn. We prove that all 4-colourings of Hn are Kempe equivalent up to \lfloor (13n)/(2) \rfloor Kempe changes. %3n (\lfloor (9n)/(2) \rfloor and \lfloor (13n)/(2) \rfloor) Kempe changes, for n ≡ 0 (mod 3) (n ≡ 2 (mod 3) and n ≡ 1 (mod 3), respectively).