The existence of Kotzig-frames in cyclically 4-edge-connected cubic graphs

A cubic graph is a graph in which every vertex has degree 33. A graph is cyclically 44-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 33-edge-coloring such that each bicolored cycle is hamiltonian. For a 22-connected cubic graph GG, a Kotzig-frame is a spanning subgraph FF such that every component of FF 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 44-edge connected cubic graph has a Kotzig-frame.

The paper notes that no cyclically 44-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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.