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

From papers

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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.