The two-orientation deletability conjecture for cubic 3-edge-connected graphs

Let GG be a cubic 33-edge-connected graph. An orientation DD of GG is strongly connected when every vertex is reachable from every other vertex by a directed path. An arc aa is deletable from DD when DaD-a is strongly connected.

Two-orientation deletability conjecture. For every cubic 33-edge-connected graph GG, there exist two strongly connected orientations D1D_1 and D2D_2 of GG such that for every vertex vv, there exist two arcs av1a^1_v and av2a^2_v incident to vv such that D1av1D_1-a^1_v and D2av2D_2-a^2_v are strongly connected.

This is one of the conjectures proposed as a relaxation of the stronger conjecture that every 33-edge-connected graph has Frank number at most 33. 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

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.