The existence of Kotzig-frames in cyclically 4-edge-connected cubic graphs
The existence of Kotzig-frames in cyclically 4-edge-connected cubic graphs
A cubic graph is a graph in which every vertex has degree . A graph is cyclically -edge connected if no edge cut of fewer than four edges separates two subgraphs each containing a cycle. A Kotzig graph is a cubic graph admitting a proper -edge-coloring such that each bicolored cycle is hamiltonian. For a -connected cubic graph , a Kotzig-frame is a spanning subgraph such that every component of has an even number of vertices and every component is either a cycle or a subdivision of a Kotzig graph.
Kotzig-frame existence conjecture. Every cyclically -edge connected cubic graph has a Kotzig-frame.
The paper notes that no cyclically -edge connected cubic graph without a Kotzig-frame was known at the time. A Kotzig-frame can yield a cycle double cover under additional conditions, so establishing the conjecture would support the cycle double cover program.
Sources & referencesView supporting material
Primary source
Herbert Fleischner, Roland Häggkvist and Arthur Hoffmann-Ostenhof, “Cycle Double Covers via Kotzig Graphs”, arXiv:1701.05844 (2017).
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.