Seminár z teórie grafov - Stanislav Jendroľ (16.10.2025)
vo štvrtok 16.10.2025 o 9:50 hod. v miestnosti M 213
Prednášajúca: Stanislav Jendroľ (UPJŠ Košice)
Názov prednášky: On colorings of plane graphs with few colors
Termín: 16.10.2025, 9:50 hod., M 213
Abstrakt:
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.