The matching-deletability conjecture for 3-edge-connected graphs

About 6 years old · traced to

Let GG be a 33-edge-connected graph. A matching is a set of pairwise vertex-disjoint edges, and a 3-edge-cut is an edge cut of size three. A matching is deletable when all its edges can become deletable in one orientation, as defined in the paper. Matching-deletability conjecture. If MM is a matching of GG intersecting each 33-edge-cut of GG in at most one edge, then MM is deletable. This proposed generalization is presented as a possible route toward improving the Frank-number bound; its status is open in the supplied text.

References

Primary source

Florian Hörsch and Zoltán Szigeti, “Connectivity of orientations of 3-edge-connected graphs”, arXiv:2012.03259 (2020).

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.