Levit's matching-cycle conjecture for almost bipartite non-König–Egerváry graphs

From papers

Let GG be an almost bipartite non-König–Egerváry graph, and let CC be its unique odd cycle. A maximum matching of GG is a matching with the largest possible number of edges. Levit's matching-cycle conjecture. Every maximum matching in GG contains

V(C)2\left\lfloor \frac{\left|V(C)\right|}{2}\right\rfloor

edges belonging to CC.

This strengthens the known result that every maximum matching contains at least one edge of the unique odd cycle; the analogous assertion is not true for almost bipartite König–Egerváry graphs.

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

Kevin Pereyra, “On R-disjoint graphs: a generalization of almost bipartite non-König-Egerváry graphs”, arXiv:2603.09797 (2026).

Solutions 0

No solutions have been posted yet.