Häggkvist–Markström Kotzig spanning-minor conjecture
Häggkvist–Markström Kotzig spanning-minor conjecture
A cubic graph is a graph in which every vertex has degree three. A cubic graph is a spanning minor of a cubic graph if some subdivision of is a spanning subgraph of . 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 -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 -even-subgraph double cover. The source also notes that -edge-connectivity is insufficient and that cyclical -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
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.