Forbidden triples for perfect matchings

Katsuhiro Ota; Michael D. Plummer; Akira Saito

doi:10.1002/jgt.20529

Forbidden triples for perfect matchings

Katsuhiro Ota, Michael D. Plummer, Akira Saito

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

Abstract

Let H be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. Plummer and Saito [J Graph Theory 50 (2005), 1-12] and Fujita et al. [J Combin Theory Ser B 96 (2006), 315-324] characterized all H with |H|≤2 such that every connected H-free graph of sufficiently large even order has a perfect matching. Extending this line of research, we give the characterization in the case of |H|≤3.

Original language	English
Pages (from-to)	250-259
Number of pages	10
Journal	Journal of Graph Theory
Volume	67
Issue number	3
DOIs	https://doi.org/10.1002/jgt.20529
Publication status	Published - 2011 Jul

Keywords

forbidden subgraph
perfect matching

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1002/jgt.20529

Cite this

@article{bd37c9bb23ce44db9957811929151ff4,

title = "Forbidden triples for perfect matchings",

abstract = "Let H be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. Plummer and Saito [J Graph Theory 50 (2005), 1-12] and Fujita et al. [J Combin Theory Ser B 96 (2006), 315-324] characterized all H with |H|≤2 such that every connected H-free graph of sufficiently large even order has a perfect matching. Extending this line of research, we give the characterization in the case of |H|≤3.",

keywords = "forbidden subgraph, perfect matching",

author = "Katsuhiro Ota and Plummer, {Michael D.} and Akira Saito",

year = "2011",

month = jul,

doi = "10.1002/jgt.20529",

language = "English",

volume = "67",

pages = "250--259",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Forbidden triples for perfect matchings

AU - Ota, Katsuhiro

AU - Plummer, Michael D.

AU - Saito, Akira

PY - 2011/7

Y1 - 2011/7

N2 - Let H be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. Plummer and Saito [J Graph Theory 50 (2005), 1-12] and Fujita et al. [J Combin Theory Ser B 96 (2006), 315-324] characterized all H with |H|≤2 such that every connected H-free graph of sufficiently large even order has a perfect matching. Extending this line of research, we give the characterization in the case of |H|≤3.

AB - Let H be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. Plummer and Saito [J Graph Theory 50 (2005), 1-12] and Fujita et al. [J Combin Theory Ser B 96 (2006), 315-324] characterized all H with |H|≤2 such that every connected H-free graph of sufficiently large even order has a perfect matching. Extending this line of research, we give the characterization in the case of |H|≤3.

KW - forbidden subgraph

KW - perfect matching

UR - http://www.scopus.com/inward/record.url?scp=79957950320&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79957950320&partnerID=8YFLogxK

U2 - 10.1002/jgt.20529

DO - 10.1002/jgt.20529

M3 - Article

AN - SCOPUS:79957950320

SN - 0364-9024

VL - 67

SP - 250

EP - 259

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Forbidden triples for perfect matchings

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this