𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A pair of forbidden subgraphs and perfect matchings

✍ Scribed by Shinya Fujita; Ken-ichi Kawarabayashi; Claudio Leonardo Lucchesi; Katsuhiro Ota; Michael D. Plummer; Akira Saito

Book ID
108167395
Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
169 KB
Volume
96
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Forbidden triples for perfect matchings
Forbidden triples for perfect matchings
✍ Katsuhiro Ota; Michael D. Plummer;; Akira Saito πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 117 KB

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

Forbidden subgraphs and bounds on the si
Forbidden subgraphs and bounds on the size of a maximum matching
✍ Michael D. Plummer; Akira Saito πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 126 KB πŸ‘ 1 views

## Abstract Let __K__~1,__n__~ denote the star on __n__ + 1 vertices; that is, __K__~1,__n__~ is the complete bipartite graph having one vertex in the first vertex class of its bipartition and __n__ in the second. The special graph __K__~1,3~, called the __claw__, has received much attention in the

Pancyclicity of 3-connected graphs: Pair
Pancyclicity of 3-connected graphs: Pairs of forbidden subgraphs
✍ Ronald J. Gould; Tomasz Łuczak; Florian Pfender πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 232 KB

## Abstract We characterize all pairs of connected graphs {__X__, __Y__} such that each 3‐connected {__X__, __Y__}‐free graph is pancyclic. In particular, we show that if each of the graphs in such a pair {__X__, __Y__} has at least four vertices, then one of them is the claw __K__~1,3~, while the