Internal partitions of regular graphs

DOI10.1002/JGT.21909MaRDI QIDQ2825476zbMATH OpenOpenAlexFDO

Authors Amir Ban, Nathan Linial

Publication date 13 October 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.5246

zbMATH Keywords

cubicexternalinternalpartitionregular

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: An internal partition of an $n$-vertex graph $G=(V,E)$ is a partition of $V$ such that every vertex has at least as many neighbors in its own part as in the other part. It has been conjectured that every $d$-regular graph with $n>N(d)$ vertices has an internal partition. Here we prove this for $d=6$. The case $d=n-4$ is of particular interest and leads to interesting new open problems on cubic graphs. We also provide new lower bounds on $N(d)$ and find new families of graphs with no internal partitions. Weighted versions of these problems are considered as well.

Recommendations

• Weak internal partition of regular graphs
• Cycle partitions of regular graphs
• Asymptotically almost every \(2r\)-regular graph has an internal partition
• Some results of regular graphs on the existence of balanced partition
• On the path partition number of 6‐regular graphs

Cites work

• Algorithmic approach to the satisfactory graph partitioning problem
• Contagion
• Graph decomposition with constraints on the connectivity and minimum degree
• scientific article; zbMATH DE number 1933255 (Why is no real title available?)
• scientific article; zbMATH DE number 944226 (Why is no real title available?)
• On decomposition of triangle-free graphs under degree constraints
• Problems and results on judicious partitions
• Satisfactory graph partition, variants, and generalizations
• The satisfactory partition problem

Cited in

(26)

• Weak internal partition of regular graphs
• 2-bisections in claw-free cubic multigraphs
• A note on 2-bisections of claw-free cubic graphs
• A characterization of weight-regular partitions of graphs
• Interior vertices in set partitions
• Isomorphic bisections of cubic graphs
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• A generalization of Stiebitz-type results on graph decomposition
• On 3-bisections in cubic and subcubic graphs
• A note on partitions of graphs under degree constraints
• A note on 3-bisections in subcubic graphs
• Asymptotically almost every \(2r\)-regular graph has an internal partition
• On problems about judicious bipartitions of graphs
• A 2-bisection with small number of monochromatic edges of a claw-free cubic graph
• Friendly bisections of random graphs
• Ban–Linial's Conjecture and treelike snarks
• A note on internal partitions: the 5-regular case and beyond
• Graph partitions under average degree constraint
• Weak external bisections of regular graphs
• Partitioning problems via random processes
• On 2-bisections and monochromatic edges in claw-free cubic multigraphs
• A note on 2-quasi-bisection of cubic graphs with oddness 2
• Partition of graphs with maximum degree ratio
• Partitioning the projective plane into two incidence-rich parts
• Faster exponential algorithms for cut problems via geometric data structures
• Ban-Linial's conjecture and Halin snarks

This page was built for publication: Internal partitions of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2825476)