The finiteness conjecture for regular graphs without internal partitions

Let d?d\text{?} be a natural number, and let a nontrivial internal partition of a graph be a partition into two nonempty parts in which every vertex has at least half of its neighbours in the same part as itself. Finiteness conjecture for regular graphs without internal partitions. For every dNd\in\mathbb{N}, there are only finitely many dd-regular graphs with no nontrivial internal partition. Internal partitions are equivalent to locally stable two-colourings, and the conjecture asserts that regular graphs lacking such a nontrivial partition are exceptional. The source says it first appeared in print in Ban and Linial and had previously been posed by DeVos; its status is open.

Sources & referencesView supporting material

Primary source

Michael Anastos, Oliver Cooley, Mihyun Kang and Matthew Kwan, “Partitioning problems via random processes”, arXiv:2307.06453 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.