Favaron–Shi minimum-degree conjecture for minimal factor-critical graphs

Let GG be a kk-factor-critical graph, meaning that deleting any kk vertices leaves a graph with a perfect matching. Call GG minimal if deleting any edge produces a graph that is not kk-factor-critical. Write (G)(G) for the minimum vertex degree of GG.

Favaron–Shi's conjecture. If GG is a minimal kk-factor-critical graph, then

δ(G)=k+1.\delta(G)=k+1.

The conjecture was posed by Favaron and Shi and concerns the sharpness of the general lower bound on the minimum degree of minimal kk-factor-critical graphs. It is known for several values of kk, including k=1k=1, k{n6,n4,n2}k\in\{n-6,n-4,n-2\}, and k{2,n10,n8}k\in\{2,n-10,n-8\}, as well as for claw-free graphs; the source proves it for planar graphs.

Sources & referencesView supporting material

Primary source

Qiuli Li, Fuliang Lu and Heping Zhang, “On minimal k-factor-critical planar graphs”, arXiv:2511.08137 (2025).

Additional references

3 papers in this index state this conjecture (2022–2025). The statement above is taken from the most recent of them; the others are arXiv:2305.06503, arXiv:2207.03120.

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.