Matchings in 3-vertex-critical graphs: The odd case Original Research Article

A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by image and called the domination number of G. Graph G is said to be image-vertex-critical if image, for every vertex image in G. A graph G is said to be factor-critical if image has a perfect matching for every choice of image. In this paper, we present two main results about 3-vertex-critical graphs of odd order. First we show that any such graph with positive minimum degree and at least 11 vertices which has no induced subgraph isomorphic to the bipartite graph image must contain a near-perfect matching. Secondly, we show that any such graph with minimum degree at least three which has no induced subgraph isomorphic to the bipartite graph image must be factor-critical. We then show that these results are best possible in several senses and close with a conjecture.