
Partitioning planar graphs with girth at least $ 9 $ into an edgeless graph and a graph with bounded size components
Author(s) -
Chao Tian,
Lei Sun
Publication year - 2021
Publication title -
mathematical modelling and control
Language(s) - English
Resource type - Journals
ISSN - 2767-8946
DOI - 10.3934/mmc.2021012
Subject(s) - combinatorics , mathematics , planar graph , partition (number theory) , bounded function , graph , vertex (graph theory) , girth (graph theory) , outerplanar graph , discrete mathematics , voltage graph , line graph , mathematical analysis
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.