The two-orientation deletability conjecture for cubic 3-edge-connected graphs
The two-orientation deletability conjecture for cubic 3-edge-connected graphs
Let be a cubic -edge-connected graph. An orientation of is strongly connected when every vertex is reachable from every other vertex by a directed path. An arc is deletable from when is strongly connected.
Two-orientation deletability conjecture. For every cubic -edge-connected graph , there exist two strongly connected orientations and of such that for every vertex , there exist two arcs and incident to such that and are strongly connected.
This is one of the conjectures proposed as a relaxation of the stronger conjecture that every -edge-connected graph has Frank number at most . The source gives no resolution, so it remains open.
Sources & referencesView supporting material
Primary source
János Barát and Zoltán L. Blázsik, “Quest for graphs of Frank number 3”, arXiv:2209.08804 (2022).
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.