Internal Partitions of Regular Graphs

DOI10.1002/jgt.21909zbMath1346.05223arXiv1307.5246OpenAlexW1928688168MaRDI QIDQ2825476

Nathan Linial, Amir Ban

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

partitionregularcubicexternalinternal

Mathematics Subject Classification ID

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

Related Items (16)

Friendly bisections of random graphs ⋮ Ban–Linial's Conjecture and treelike snarks ⋮ Weak internal partition of regular graphs ⋮ A note on partitions of graphs under degree constraints ⋮ A note on internal partitions: the 5-regular case and beyond ⋮ A note on 3-bisections in subcubic graphs ⋮ A 2-bisection with small number of monochromatic edges of a claw-free cubic graph ⋮ Graph partitions under average degree constraint ⋮ 2-bisections in claw-free cubic multigraphs ⋮ Isomorphic bisections of cubic graphs ⋮ A note on 2-bisections of claw-free 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 ⋮ Asymptotically almost every \(2r\)-regular graph has an internal partition ⋮ On problems about judicious bipartitions of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Satisfactory graph partition, variants, and generalizations
• Algorithmic approach to the satisfactory graph partitioning problem
• The satisfactory partition problem
• Graph decomposition with constraints on the connectivity and minimum degree
• On decomposition of triangle-free graphs under degree constraints
• Problems and results on judicious partitions
• Contagion

This page was built for publication: Internal Partitions of Regular Graphs