The finiteness conjecture for regular graphs without internal partitions
The finiteness conjecture for regular graphs without internal partitions
Let 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 , there are only finitely many -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.