z-logo
open-access-imgOpen Access
Partitioning planar graphs with girth at least $ 9 $ into an edgeless graph and a graph with bounded size components
Author(s) -
Chunyu 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) , discrete mathematics , 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom