3
$\begingroup$

The Question: Let $G$ be a (simple) graph and let $b\in\mathbb{N}$. Suppose that we have $b$ disjoint edge-subsets $M_1,\ldots , M_b$ satisfying the following condition: The set $M_1$ is a maximal matching in $G$. For each $1< i\leq b$, the set $M_i$ is a maximal matching in the graph $G\setminus (M_1\cup\ldots\cup M_{i-1})$.

What can we say about the size of $M_1\cup\ldots\cup M_b$ compared to the size of a maximum $b$-matching? In particular, if $M$ is a maximum $b$-matching in $G$, is there anything known about the ratio $\frac{\vert M_1\cup\ldots\cup M_b \vert}{\vert M\vert}$ ?

Observations: A $b$-matching is a subset of edges $M$ such that the subgraph induced by $M$ has maximum degree $b$. A maximal $b$-matching must always be at least half the size of a maximum $b$-matching. However, the stated condition does not in general imply that $M_1\cup \ldots \cup M_b$ is a maximal $b$-matching in $G$. For $b=1,2$ it is not difficult to show that the ratio must be at least $\frac12$.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.