Decomposing Complete Graphs into Bounded-Degree Regular Factors

Definitions and mathematical statement

Use the usual interpretation of a graph as a finite undirected simple graph; this convention is implicit rather than explicitly specified in the supplied record. Let $K_n$ be the complete graph on $n$ vertices. A graph is $r$-regular if every vertex has degree $r$. A decomposition of $K_n$ into graphs $F_1,\ldots,F_t$ means that there are spanning subgraphs $H_1,\ldots,H_t\subseteq K_n$ such that \[ H_i\cong F_i\quad(1\le i\le t),\qquad E(K_n)=\mathop{\dot\bigcup}_{i=1}^{t}E(H_i). \] Thus the factors are copies of the prescribed graphs, with pairwise disjoint edge sets covering every edge of $K_n$.

Supplied conjectural statement. For every positive integer $\Delta$, does there exist a positive integer $n_0=n_0(\Delta)$ such that, for every integer $n\ge n_0$, every positive integer $t$, and every family $F_1,\ldots,F_t$ of graphs each having exactly $n$ vertices, if $F_i$ is $r_i$-regular for each $i$, where \[ 0\le r_i\le\Delta\quad(1\le i\le t),\qquad \sum_{i=1}^{t}r_i=n-1, \] then $K_n$ has a decomposition into $F_1,\ldots,F_t$? No separate parity restriction on $n$ is imposed; the quantified families must themselves exist as regular graphs. Zero-degree factors, if allowed, are spanning edgeless graphs and impose no edge requirement.

Unresolved source qualification. The supplied record marks its statement status as unrecoverable and supplies no clean statement. Its verification note nevertheless reports that the official report confirms this conjecture and identifies it as a duplicate of the earlier canonical record OWR-16763-018. The formulation above renders the supplied original statement and does not establish a distinct conjecture or independently verify that identification. The graph convention and treatment of zero-degree factors require confirmation against the original source.

Short English statement

For each fixed degree bound, the question asks whether every sufficiently large complete graph can be partitioned into prescribed spanning regular graphs whose degrees obey that bound and sum to the complete graph's degree. The supplied record labels the conjecture open, but also marks this entry as an unrecoverable duplicate of OWR-16763-018; both qualifications are retained pending human review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004129$, title "Decomposing Complete Graphs into Bounded-Degree Regular Factors," exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The proposed year is recorded as 2019; no proposer is supplied. The record preserves the original statement, has no clean statement, and gives statement status unrecoverable. Its supplied verification note identifies the conjecture with the earlier canonical record OWR-16763-018; no permanent numeric ID for that earlier record is supplied.
• Supplied report citation: Combinatorics, Probability and Computing (2020), Oberwolfach Reports, pp. 1113--1189, DOI 10.4171/owr/2019/19. https://doi.org/10.4171/owr/2019/19. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature reference: Glock--Joos--Kim--Kuhn--Osthus, Resolution of the Oberwolfach problem. https://doi.org/10.4171/JEMS/1060.
• Supplied literature reference: Oberwolfach Report 19/2019, Conjecture 3. https://doi.org/10.4171/owr/2019/19.
• Literature assessment dated 2026-08-22: the supplied curation labels the problem open, describes the bounded-degree regular-factor decomposition as a conjecture beyond the large-cycle-factor theorem, and reports that no complete proof of the general statement was found. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment. The background expressly requests independent verification of time-sensitive status and cited claims.