Hoang La, Borut Lužar, Kenny Štorgel

The Grötzsch Theorem states that every triangle-free planar graph G admits a proper 3-coloring, i.e. a coloring of the vertices of G with three colors such that adjacent vertices are assigned distinct colors. However, we may also allow triangles in general planar graphs and still retain 3-colorability. Havel conjectured that a 3-colorable planar graph may contain arbitrarily many triangles as long as they are su ciently far apart. This conjecture was proved by Dvořák, Král’, and Thomas. On the other hand, there are 3-colorable planar graphs that may have close triangles (even incident). A result by Dross et al. states that every planar graph obtained as a subgraph of the medial graph of a bipartite plane graph is 3-colorable.

As mentioned, the Grötzsch Theorem has many generalizations, although, perhaps the most well-known is a result of Grünbaum and Aksenov, giving 3-colorability of planar graphs with at most three triangles, which is in general best possible. A lot of attention was also given to extending 3-colorings of subgraphs of triangle-free planar graphs to the whole graph. In particular, a result of Aksenov, Borodin, and Glebov states that we can precolor any two non-adjacent vertices in a triangle-free planar graph and retain 3-colorability. Furthermore, several other results exist which deal with precolorings of a face of certain length in a triangle-free planar graph.

In this talk, we will present the above-mentioned results and provide further extensions of the Grötzsch Theorem by considering 3-colorings of planar graphs with at most one triangle. In particular, we show that a precoloring of any two non-adjacent vertices and a precoloring of a face of length at most 4 can be extended to a 3-coloring of the whole graph. Additionally, we show that for every vertex of degree at most 3 in a planar graph with at most one triangle, a precoloring of its neighborhood with the same color extends to a 3-coloring of the whole graph. The latter result yields an a rmative answer to a conjecture on adynamic coloring.

Our Math Research Seminar will not be broadcasted via Zoom this time.

 See you there!

 Everyone is welcome and encouraged to attend.