Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths |
| |
| Authors: | Maria Axenovich Torsten Ueckerdt Pascal Weiner |
| |
| Affiliation: | 1. KARLSRUHE INSTITUTE OF TECHNOLOGY, DEPARTMENT OF MATHEMATICS, KARLSRUHE, GERMANYAuthor supported;2. KARLSRUHE INSTITUTE OF TECHNOLOGY, DEPARTMENT OF MATHEMATICS, KARLSRUHE, GERMANY |
| |
| Abstract: | Recently, Borodin, Kostochka, and Yancey (Discrete Math 313(22) (2013), 2638–2649) showed that the vertices of each planar graph of girth at least 7 can be 2‐colored so that each color class induces a subgraph of a matching. We prove that any planar graph of girth at least 6 admits a vertex coloring in  colors such that each monochromatic component is a path of length at most 14. Moreover, we show a list version of this result. On the other hand, for each positive integer  , we construct a planar graph of girth 4 such that in any coloring of vertices in  colors there is a monochromatic path of length at least t. It remains open whether each planar graph of girth 5 admits a 2‐coloring with no long monochromatic paths. |
| |
| Keywords: | planar graph decomposition defective coloring fragmented coloring path forests 2‐coloring |
|
|
colors such that each monochromatic component is a path of length at most 14. Moreover, we show a list version of this result. On the other hand, for each positive integer 
, we construct a planar graph of girth 4 such that in any coloring of vertices in 
colors there is a monochromatic path of length at least t. It remains open whether each planar graph of girth 5 admits a 2‐coloring with no long monochromatic paths.