Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths
| Autor: | Torsten Ueckerdt, Maria Axenovich, Pascal Weiner |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematics::Combinatorics
010102 general mathematics 0102 computer and information sciences 01 natural sciences Vertex (geometry) Planar graph Combinatorics symbols.namesake Computer Science::Discrete Mathematics 010201 computation theory & mathematics symbols Discrete Mathematics and Combinatorics Geometry and Topology Monochromatic color 0101 mathematics Mathematics |
| Zdroj: | Journal of Graph Theory. 85:601-618 |
| ISSN: | 0364-9024 |
| DOI: | 10.1002/jgt.22093 |
| Popis: | 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 two 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 t≥3, we construct a planar graph of girth 4 such that in any coloring of vertices in two 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text