Seminar of Graph Theory - Stanislav Jendroľ (16.10.2025)
Thursday 16.10.2025 at 9:50, Lecture room M 213
Stanislav Jendroľ (UPJŠ Košice):
On colorings of plane graphs with few colors
Abstract:
A facial path in a plane graph G is a subpath of the boundary walk of a face of G. The Four Color Theorem states that every plane graph contains a proper vertex 4-coloring in which each monochromatic facial path consists of exactly one vertex. Czap, Fabrici, and Jendrol’ in 2021 conjectured that every plane graph G admits an improper vertex 3-coloring (resp. 2-coloring) in which every monochromatic facial path in G has at most two vertices (resp. three vertices). In our talk we present a proof of the first conjecture. Our result is optimal. Next we will present what is a set up on the second conjecture.
References
[1] J. Czap, I. Fabrici and S. Jendrol’, Colorings of plane graphs without long monochromatic facial paths, Discuss. Math. Graph Theory 41 (2021) 801– 808.
[2] S. Jendrol’, On a 3-coloring of plane graphs without monochromatic facial 3-paths, Discuss. Math. Graph Theory, https://doi.org/10.7151/dmgt.2584.
[3] S. Jendrol’, Corrigendum to ”On a 3-coloring of plane graphs without monochromatic facial 3-path”, Discuss. Math. Graph Theory, https://doi.org/10.7151/dmgt.2602.