Asymptotically Almost Every 2r-regular Graph has an Internal Partition

2017/08/14 by Linial, Nathan, Louis, Sria
#05C70 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1708.04162

Abstract

An internal partition of a graph is a partitioning of the vertex set into two parts such that for every vertex, at least half of its neighbors are on its side. We prove that for every positive integer r, asymptotically almost every 2r-regular graph has an internal partition.

Related

• Internal Partitions of Regular Graphs
• A note on internal partitions: the 5-regular case and beyond
• Bisection width, max-cut and internal partitions of 5-regular graphs
• On a specific problem of partition of graph
• Partitioning problems via random processes