Partitioning sparse graphs into an independent set and a graph with bounded size components

2019/05/06 by Choi, Ilkyoo, Dross, François, Ochem, Pascal
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1905.02123

Abstract

We study the problem of partitioning the vertex set of a given graph so that each part induces a graph with components of bounded order; we are also interested in restricting these components to be paths. In particular, we say a graph G admits an (\cal I, \cal O_k)-partition if its vertex set can be partitioned into an independent set and a set that induces a graph with components of order at most k. We prove that every graph G with mad(G)

Related

• Partitioning sparse graphs into an independent set and a forest of\n bounded degree
• A note on independent sets in sparse-dense graphs
• A note on vertex partitions
• Partitions of Graphs into Special Bipartite Graphs
• Partitions of graphs into small and large sets