Mkrtchyan–Petrosyan–Vardanyan conjecture on maximum matchings

Let GG be a graph, possibly with multiple edges but no loops, and let Δ(G)\Delta(G) and δ(G)\delta(G) denote its maximum and minimum degrees. A matching is maximum if it has largest possible cardinality, and a vertex is MM-unsaturated if it is not incident with an edge of MM.

Mkrtchyan–Petrosyan–Vardanyan conjecture. If

Δ(G)δ(G)1,\Delta(G)-\delta(G)\le 1,

then GG contains a maximum matching MM such that no two MM-unsaturated vertices have a common neighbor.

The conjecture is refuted: Picouleau found a counterexample that is a simple bipartite graph with δ(G)=4\delta(G)=4 and Δ(G)=5\Delta(G)=5.

Sources & referencesView supporting material

Primary source

Dong Ye, “Maximum matchings in regular graphs”, arXiv:1308.2269 (2016).

Additional references

2 papers in this index state this conjecture (2012–2013). The statement above is taken from the most recent of them; the others are arXiv:1202.0681.

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.