Journal Articles Discrete Mathematics Year : 2022

Further extensions of the Grötzsch Theorem

Xuan Hoang La
Borut Lužar

Abstract

The Grötzsch Theorem states that every triangle-free planar graph admits a proper 3-coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving 3-colorability of planar graphs with at most three triangles, is perhaps the most known. A lot of attention was also given to extending 3-colorings of subgraphs to the whole graph. In this paper, we consider 3-colorings of planar graphs with at most one triangle. Particularly, we show that precoloring of any two non-adjacent vertices and precoloring of a face of length at most 4 can be extended to a 3-coloring of the graph. Additionally, we show that for every vertex of degree at most 3, a precoloring of its neighborhood with the same color extends to a 3-coloring of the graph. The latter result implies an affirmative answer to a conjecture on adynamic coloring. All the presented results are tight.
Fichier principal
Vignette du fichier
2110.01862.pdf (701) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-04041742 , version 1 (11-10-2023)

Identifiers

Cite

Xuan Hoang La, Borut Lužar, Kenny Štorgel. Further extensions of the Grötzsch Theorem. Discrete Mathematics, 2022, 345 (6), pp.#112849. ⟨10.1016/j.disc.2022.112849⟩. ⟨lirmm-04041742⟩
36 View
16 Download

Altmetric

Share

More