Levit's matching-cycle conjecture for almost bipartite non-König–Egerváry graphs
Levit's matching-cycle conjecture for almost bipartite non-König–Egerváry graphs
Let be an almost bipartite non-König–Egerváry graph, and let be its unique odd cycle. A maximum matching of is a matching with the largest possible number of edges. Levit's matching-cycle conjecture. Every maximum matching in contains
edges belonging to .
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
Sign in to submit a solution.
No solutions have been posted yet.