PreprintarXiv licencearXiv
Internal partitions of $5$-regular and $8$-regular graphs
Abstract
An \emph{internal partition} of a graph is a partition of its vertex set into two nonempty parts such that every vertex has at least half of its neighbors in its own part. DeVos asked whether, for every fixed positive integer r, all but finitely many r-regular graphs admit an internal partition. This was previously known to hold only for r∈{3,4,6}. In this paper, we confirm this for r∈{5,8} by proving that every r-regular graph on at least 107 vertices has an internal partition.
Related
- Perfect Partitions of Regular Bipartite Graphs
- On the growth of weak regular partitions in k-uniform hypergraphs
- Characterizations and MacWilliams-Like Identities of Weakly Regular Bent Partitions
- The minimal excludant and the least r-gaps of ℓ-regular partitions
- Unfriendly partitions of locally finite Borel graphs
BibTeX
@misc{lin2026internal,
title = {{Internal partitions of $5$-regular and $8$-regular graphs}},
author = {Siwei Lin and Qinghou Zeng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19014},
eprint = {2610.19014},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19014},
}
RIS
TY - UNPB
TI - Internal partitions of $5$-regular and $8$-regular graphs
AU - Siwei Lin
AU - Qinghou Zeng
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.19014
UR - https://arxiv.org/abs/2610.19014
AB - An \emph{internal partition} of a graph is a partition of its vertex set into two nonempty parts such that every vertex has at least half of its neighbors in its own part. DeVos asked whether, for every fixed positive integer r, all but finitely many r-regular graphs admit an internal partition. This was previously known to hold only for r∈{3,4,6}. In this paper, we confirm this for r∈{5,8} by proving that every r-regular graph on at least 10^7 vertices has an internal partition.
ER -