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

At least 3 years old · documented by

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 D−aD-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 D1−av1D_1-a^1_v and D2−av2D_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.

References

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.