High girth and extendability (Q1918540)

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.