Matchings in 3-vertex-critical graphs: The odd case

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 γ(G)γ(G) and called the domination number of G. Graph G   is said to be γγ-vertex-critical if γ(G-v)<γ(G)γ(G-v)<γ(G), for every vertex vv in G. A graph G   is said to be factor-critical if G-vG-v has a perfect matching for every choice of v∈V(G)v∈V(G).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 K1,5K1,5 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 K1,4K1,4 must be factor-critical. We then show that these results are best possible in several senses and close with a conjecture.