Partitioning planar graphs with girth at least 9 into an edgeless graph and a graph with bounded size components

Abstract

In this paper, we study the problem of partitioning the vertex set of a planar graph with girth restriction into parts, also referred to as color classes, such that each part induces a graph with components of bounded order. An ($ \mathcal{I} $, $ \mathcal{O}_{k} $)-partition of a graph $ G $ is the partition of $ V(G) $ into two non-empty subsets $ V_{1} $ and $ V_{2} $, such that $ G[V_{1}] $ is an edgeless graph and $ G[V_{2}] $ is a graph with components of order at most $ k $. We prove that every planar graph with girth 9 and without intersecting $ 9 $-face admits an ($ \mathcal{I} $, $ \mathcal{O}_{6} $)-partition. This improves a result of Choi, Dross and Ochem (2020) which says every planar graph with girth at least $ 9 $ admits an ($ \mathcal{I} $, $ \mathcal{O}_{9} $)-partition.

Keywords

• planar graph
• girth
• face
• vertex partition
• discharging procedure