Häggkvist–Markström Kotzig spanning-minor conjecture

A cubic graph is a graph in which every vertex has degree three. A cubic graph HH is a spanning minor of a cubic graph GG if some subdivision of HH is a spanning subgraph of GG. A Kotzig graph is a cubic graph with a 3-edge-coloring such that the union of any two color classes is a Hamilton circuit.

Häggkvist–Markström conjecture. Every 33-connected cubic graph contains a Kotzig graph as a spanning minor.

The conjecture would provide a broad sufficient condition for the circuit double cover conjecture, because a cubic graph containing a Kotzig graph as a spanning minor has a 66-even-subgraph double cover. The source also notes that 33-edge-connectivity is insufficient and that cyclical 44-edge-connectivity may be necessary.

Sources & referencesView supporting material

Primary source

Dong Ye and Cun-Quan Zhang, “Cycle Double Covers and Semi-Kotzig Frame”, arXiv:1105.5190 (2011).

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.