On maximum matchings in almost regular graphs
read the original abstract
In 2010, Mkrtchyan, Petrosyan and Vardanyan proved that every graph $G$ with $2\leq \delta(G)\leq \Delta(G)\leq 3$ contains a maximum matching whose unsaturated vertices do not have a common neighbor, where $\Delta(G)$ and $\delta(G)$ denote the maximum and minimum degrees of vertices in $G$, respectively. In the same paper they suggested the following conjecture: every graph $G$ with $\Delta(G)-\delta(G)\leq 1$ contains a maximum matching whose unsaturated vertices do not have a common neighbor. Recently, Picouleau disproved this conjecture by constructing a bipartite counterexample $G$ with $\Delta(G)=5$ and $\delta(G)=4$. In this note we show that the conjecture is false for graphs $G$ with $\Delta(G)-\delta(G)=1$ and $\Delta(G)\geq 4$, and for $r$-regular graphs when $r\geq 7$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.