On a specific problem of partition of graph

2023/08/14 by Yu, Peisheng
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2308.07349

Abstract

In this short article, we consider a problem about 2-partition of the vertices of a graph. If a graph admits such a partition into some 'small' graphs, then the number of edges cross an arbitrary cut of the graph e(S,S^c) has a nice lower bound.

Related

• Partitions of Graphs into Special Bipartite Graphs
• A graph partition problem
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
• Edge Partitions of Complete Geometric Graphs (Part 2)
• Bisections of graphs