Publications
Sort:
Open Access Research Article Issue
Partitioning planar graphs with girth at least 9 into an edgeless graph and a graph with bounded size components
Mathematical Modelling and Control 2021, 1(3): 136-144
Published: 15 September 2021
Abstract PDF (294 KB) Collect
Downloads:0

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 ( I, Ok)-partition of a graph G is the partition of V(G) into two non-empty subsets V1 and V2, such that G[V1] is an edgeless graph and G[V2] 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 ( I, O6)-partition. This improves a result of Choi, Dross and Ochem (2020) which says every planar graph with girth at least 9 admits an ( I, O9)-partition.

Total 1