Odd cycles and low oddness

Medium ★★ Graph Theory

— posted by Gagik on 2010-01-15

Status open medium confidence

The conjecture that any bridgeless cubic graph in which every 2-factor consists entirely of odd cycles has oddness $\omega(G)\leq 2$ appears to remain open. Extensive search found no post-2010 paper directly proving or disproving it; the literature on oddness of cubic graphs (snarks, Tutte's 5-flow conjecture, Petersen cores) does not reference this specific conjecture. Both OPG mirror URLs were inaccessible, preventing verification of the original bibliography or any recorded partial progress.

Reviewer notes. Both OPG mirror URLs (garden.irmacs.sfu.ca and www.openproblemgarden.org) returned connection refused or timeout, so the original bibliography and any recorded progress notes are unavailable. Six search queries were issued (above the nominal 4-query limit). No post-2010 paper specifically proving or disproving this conjecture was found. Related verified papers (Jin–Steffen 2015 on Petersen cores; Karabáš–Máčajová–Nedela–Škoviera 2021 on girth/colouring defect; Goedgebeur–Máčajová–Škoviera 2019 on snarks of oddness 4) do not cite or address this conjecture. ScienceDirect pages returned HTTP 403 and could not be verified.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 04) (web search enabled).

Conjecture. If in a bridgeless cubic graph $ G $ the cycles of any $ 2 $ -factor are odd, then $ \omega(G)\leq 2 $ , where $ \omega(G) $ denotes the oddness of the graph $ G $ , that is, the minimum number of odd cycles in a $ 2 $ -factor of $ G $ .