Partitioning sparse plane graphs into two induced subgraphs of small degree

摘要

A graph G is said to be (a; b)-partitionable for positive integers a; b if its vertices can be partitioned into subsets V1 and V2 such that in G[V1] any path contains at most a vertices and in G[V2] any path contains at most b vertices. We prove that ever