Affordable Access

Publisher Website

Forbidden induced subgraphs for near perfect matchings

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
313
Issue
11
Identifiers
DOI: 10.1016/j.disc.2013.01.020
Keywords
  • Near Perfect Matching
  • Perfect Matching
  • Forbidden Subgraph

Abstract

Abstract Let F be a family of connected graphs. A graph G is said to be F-free if G is H-free for every graph H in F. Fujita et al. (2006) [2] studied the problem of characterizing the families of graphs F such that every large enough connected F-free graph of odd order has a near perfect matching. In the same work, the authors characterized such families F, but in the case where every graph in F is triangle-free. In this paper, we complete the characterization of all such families, removing the triangle-free condition.

There are no comments yet on this publication. Be the first to share your thoughts.