Paperlane

no. 7 · Tuesday 3 November 2026

Total dominating sets and four-colorings of planar triangulations

Hyemin Kwon, Boram Park and Yoshio Sano

math.CO · 12 pp

Abstract

In 2018, Goddard and Henning conjectured that every planar triangulation on at least four vertices has two disjoint total dominating sets. It was proved by Francis, Illickan, Jose, and Rajendraprasad in 2024. As a strengthening of this result, Goddard and Henning also conjectured that every planar triangulation with at least four vertices has a proper $4$-coloring with color classes $C_1,C_2,C_3,C_4$ such that $C_1\cup C_2$ and $C_3\cup C_4$ are total dominating sets. In this paper, we disprove this conjecture: for every $n\ge 36$ there is a planar triangulation with $n$ vertices without such a coloring. As another strengthening of the result by Francis, Illickan, Jose, and Rajendraprasad, they conjectured that every near-triangulation has a $4$-coloring, not necessarily proper, in which every vertex $v$ sees at least $\min \{ \operatorname{deg}(v),3 \}$ colors on its neighbors. We prove this conjecture for all planar triangulations.

comments
12 pages, 3 figures
fields
Combinatorics
pdf ↗ page arXiv:2611.00572 ↗