Colorings of Plane Graphs Without Long Monochromatic Facial Paths

Abstract

Let G be a plane graph. A facial path of G is a subpath of the boundary walk of a face of G. We prove that each plane graph admits a 3-coloring (a 2-coloring) such that every monochromatic facial path has at most 3 vertices (at most 4 vertices). These results are in a contrast with the results of Chartrand, Geller, Hedetniemi (1968) and Axenovich, Ueckerdt, Weiner (2017) which state that for any positive integer t there exists a 4-colorable (a 3-colorable) plane graph Gt such that in any its 3-coloring (2-coloring) there is a monochromatic path of length at least t. We also prove that every plane graph is 2-list-colorable in such a way that every monochromatic facial path has at most 4 vertices.

Keywords

• plane graph
• facial path
• vertex-coloring
• 05c10
• 05c15