Further extensions of the Grötzsch Theorem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Mathematics Year : 2022

Further extensions of the Grötzsch Theorem

Xuan Hoang La
  • Function : Author
  • PersonId : 1077186
  • IdRef : 264820797
Borut Lužar


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.44 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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



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⟩
27 View
4 Download



Gmail Facebook X LinkedIn More