Regular Graphs Without Isomorphic Bisections
math.CO
Submitted: 2026-10-26
Updated: 2026-10-26
License: http://creativecommons.org/licenses/by/4.0/
The gist: A graph is bisectable if its vertex set can be split into two sets inducing isomorphic subgraphs.
Abstract
A graph is bisectable if its vertex set can be split into two sets inducing isomorphic subgraphs. Ando conjectured that every cubic graph is bisectable, and Das, Pokrovskiy, and Sudakov proved it for large enough connected cubic graphs. We give a constructive proof that, for every d at least5, there exists a non-bisectable d-regular graph of even order.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality