Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/76607
Type: Artigo de periódico
Title: A pair of forbidden subgraphs and perfect matchings
Author: Fujita, S
Kawarabayashi, K
Lucchesi, CL
Ota, K
Plummer, MD
Saito, A
Abstract: In this paper, we study the relationship between forbidden subgraphs and the existence of a matching. Let W be a set of connected graphs. each of which has three or more vertices. A graph G is said to be H-free if no graph in W is ail induced subgraph of G. We completely characterize the set H such that every connected H-free graph of sufficiently large even order has a perfect matching in the following cases. (1) Every graph in R is triangle-free. (2) H consists of two graphs (i.e. a pair of forbidden subgraphs). A matching M in a graph of odd order is said to be a near-perfect matching if every vertex of G but one is incident with an edge of M. We also characterize H such that every H-free graph of sufficiently large odd order has a near-perfect matching in the above cases. (C) 2005 Elsevier Inc. All rights reserved.
Subject: perfect matching
near-perfect matching
forbidden subgraph
Country: EUA
Editor: Academic Press Inc Elsevier Science
Rights: fechado
Identifier DOI: 10.1016/j.jctb.2005.08.002
Date Issue: 2006
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000237476800001.pdf168.75 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.