Fork Graphs and Directed Cycle Double Covers

Definitions and mathematical statement

An undirected graph is cubic if every vertex has degree three, and bridgeless if deleting any single edge does not increase its number of connected components.

For a loopless undirected graph $G$, a directed cycle double cover is an indexed family of cycles of the underlying undirected graph, each equipped with a cyclic orientation, such that every edge occurs exactly once in each of its two directions. Repeated members are counted with multiplicity. Traversing a single edge in both directions does not constitute a cycle for this definition. This describes the usual loopless formulation; the supplied record does not specify finiteness, simplicity, or conventions concerning loops, parallel edges, and admissible cycle lengths, so it does not determine the full intended graph domain.

Let $\mathcal F$ denote the intended class of fork graphs. This notation is a placeholder: the supplied record contains no definition or construction of fork graphs, and hence does not provide a membership criterion for $\mathcal F$. The directed cycle double cover assertion for this class would have the form \[ \forall G\in\mathcal F,\qquad G\text{ admits a directed cycle double cover}, \] once the class and graph conventions have been specified. The corresponding assertion for general cubic bridgeless graphs replaces $\mathcal F$ by that graph class under the same conventions.

Source question. How rich is the class of fork graphs, and is the directed cycle double cover conjecture as hard for fork graphs as for general cubic bridgeless graphs?

The normalized statement also uses "How numerous" in place of "How rich." Neither wording specifies a counting function, a structural criterion for richness, or a measure of abundance. Likewise, "as hard" does not specify a logical reduction, an algorithmic reduction, or another comparison. Consequently, the supplied evidence determines this question but does not determine a precise enumeration problem or a formal equivalence or reduction statement. Such a statement requires the missing definition of fork graphs and a specified interpretation of both comparisons.

Short English statement

The problem asks how extensive the class of fork graphs is and whether resolving the directed cycle double cover conjecture for that class captures the difficulty of resolving it for all cubic bridgeless graphs. A directed cycle double cover uses every edge once in each direction along oriented graph cycles. The record omits the definition of fork graphs and precise meanings of "rich" and "as hard," so a fully quantified target cannot yet be recovered.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002275$, title Fork Graphs and Directed Cycle Double Covers, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection; proposed year: 2013. No problem proposer is identified in the record.
• Graph Theory (2013), Oberwolfach Reports, DOI 10.4171/owr/2013/02, pp. 67--128. Supplied source report and literature-source link: https://doi.org/10.4171/owr/2013/02. The record describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Jiménez--Loebl, described in the supplied literature sources as "directed cycle double cover conjecture for fork graphs": https://arxiv.org/abs/1310.5539. This supplied paper attribution does not identify the proposer of the source question.
• Supplied literature assessment dated 2026-08-21: status labeled open; the primary paper is reported to prove Jaeger's conjecture only for lean fork-graphs, while the general fork-graph claim and the directed cycle double cover conjecture are reported to remain unresolved. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment. The supplied background expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that its mathematical content was checked against the official report, with notation, context, and question form normalized without changing the source-level claim. That verification is reported provenance; the cited sources have not been independently inspected for this draft.