Pairs of disjoint matchings and related classes of graphs (Q6117063)
From MaRDI portal
scientific article; zbMATH DE number 7714189
Language | Label | Description | Also known as |
---|---|---|---|
English | Pairs of disjoint matchings and related classes of graphs |
scientific article; zbMATH DE number 7714189 |
Statements
Pairs of disjoint matchings and related classes of graphs (English)
0 references
19 July 2023
0 references
For a finite graph \(G\), let \[ \lambda(G): =\max\{|H|+|H^\prime|: H \text{ and } H^\prime \text{ are disjoint matchings in } G\}, \] and \[ \mu(G): =\max\{|H|: H \text{ and } H^\prime \text{ are disjoint matchings in } G\text{ with } |H|+|H^\prime|=\lambda(G)\}. \] Some research concerned with the ratio \(\mu(G)/\nu(G)\) of two parameters of a graph \(G\), where \(\nu(G)\) is the matching number, and \(\mu(G)\) is the size of a maximum matching in \(G\). \textit{V. V. Mkrtchyan} et al. [Discrete Math. 308, No. 23, 5823--5828 (2008; Zbl 1204.05080)] proved that \(\frac{4}{5}\leq \mu(G)/\nu(G)\leq 1\) for any graph \(G\), and \textit{A. Tserunyan} [ibid. 309, No. 4, 693--713 (2009; Zbl 1170.05049)] characterized all graphs that achieve the ratio \(4/5\). This paper under review obtains two interesting results as follows: For any positive integers \(m\), \(n\) such that \(4/5 < m/n < 1\), there is a connected graph \(G\) with \(\mu(G) = m\) and \(\nu(G) = n\). If a finite connected graph \(G\) has \(\mu(G)/\nu(G) < 1\), then it contains a diamond spanner as a subgraph. Further, it points out an open problem: Give a structural characterization of the class of all finite connected graphs \(G\) with \(\mu(G)/\nu(G) = 1\).
0 references
graph matching
0 references
edge coloring
0 references
maximum 2-edge colorable subgraph
0 references
0 references