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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    graph matching
    0 references
    edge coloring
    0 references
    maximum 2-edge colorable subgraph
    0 references

    Identifiers