Name
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 G(t) 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.7151/dmgt.2319 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | DocType | Volume |
plane graph, facial path, vertex-coloring | Journal | 41 |
Issue | ISSN | Citations |
3 | 1234-3099 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Július Czap | 1 | 80 | 15.40 |
| Igor Fabrici | 2 | 101 | 14.64 |
| Stanislav Jendrol' | 3 | 283 | 38.72 |