zbMATH — the first resource for mathematics

Path partitions of planar graphs. (Russian. English summary) Zbl 1132.05315
Summary: A graph \(G\) is said to be \((a, b)\)-partitionable for positive integers \(a, b\) if its vertices can be partitioned into subsets \(V_1, V_2\) such that in \(G[V_1]\) any path contains at most \(a\) vertices and in \(G[V_2]\) any path contains at most \(b\) vertices. Graph \(G\) is \(\tau\)-partitionable if it is \((a, b)\)-partitionable for any \(a, b\) such that \(a+b\) is the number of vertices in the longest path of \(G\). We prove that every planar graph of girth 5 is \(\tau\)-partitionable and that planar graphs with girth 8, 9 and 16 are \((2, 3)\)-, \((2, 2)\)-, and \((1, 2)\)-partitionable respectively.

05C15 Coloring of graphs and hypergraphs
Full Text: Link EuDML