Total dominating sets and four-colorings of planar triangulations
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 C1,C2,C3,C4 such that C1∪ C2 and C3∪ C4 are total dominating sets. In this paper, we disprove this conjecture: for every n≥ 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 { deg(v),3 } colors on its neighbors. We prove this conjecture for all planar triangulations.
Related
- Every cubic graph has four total dominating sets covering each vertex at most twice
- Total eight-colorings of maximal planar graphs of maximum degree six
- Notes on efficient dominating sets and efficient open dominating sets in circulant graphs
- Prime Nullspace Matrices and Even Dominating Sets
- On the local average order of dominating sets
BibTeX
@misc{kwon2026total,
title = {{Total dominating sets and four-colorings of planar triangulations}},
author = {Hyemin Kwon and Boram Park and Yoshio Sano},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00572},
eprint = {2611.00572},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00572},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Total dominating sets and four-colorings of planar triangulations
AU - Hyemin Kwon
AU - Boram Park
AU - Yoshio Sano
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00572
UR - https://arxiv.org/abs/2611.00572
AB - 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∪ C_2 and C_3∪ C_4 are total dominating sets. In this paper, we disprove this conjecture: for every n≥ 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 { deg(v),3 } colors on its neighbors. We prove this conjecture for all planar triangulations.
ER -