# 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.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text: