High girth and extendability
A graph \(G\) is said to be \(k\)-extendable if \(G\) contains a perfect matching, has more than \(2k\) vertices, and every matching of size \(k\) can be extended to a perfect matching. This concept was introduced by \textit{M. D. Plummer} [Discrete Math. 31, 201-210 (1980; Zbl 0442.05060)]. The main result is that for positive integers \(n\) and \(k\) there is a \(k\)-extendable graph with girth greater than \(n\). The authors point out that Euler's formula easily implies that for every \(\chi\) there exists \(k(\chi)\) such that every graph of genus \(\chi\) and girth \(k(\chi)\) fails to be 2-extendable. Their main result implies that \(k(\chi)\) is unbounded. They speculate that the problem of determining \(k(\chi)\) will not be easy. This is relevant to the result of \textit{N. Dean} [J. Comb. Theory, Ser. B 54, No. 1, 133-141 (1992; Zbl 0707.05051)] that the maximum extendability of a graph of a given genus is related to the extendability of complete bipartite graphs.
- A hypergraph-free construction of highly chromatic graphs without short cycles
- A short proof of the existence of highly chromatic hypergraphs without short cycles
- Explicit constructions of graphs without short cycles and low density codes
- Extending partial systems of distinct representatives
- Extending subpermutation matrices in regular classes of matrices
- scientific article; zbMATH DE number 3451870 (Why is no real title available?)
- scientific article; zbMATH DE number 3189017 (Why is no real title available?)
- On chromatic number of finite set-systems
- On n-extendable graphs
- Ramanujan graphs
- The Cartesian product of a \(k\)-extendable and an \(l\)-extendable graph is \((k+l+1)\)-extendable
- The matching extendability of surfaces
This page was built for publication: High girth and extendability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1918540)
