✦ LIBER ✦

Component factors and induced subgraphs

✍ Scribed by Nishimura, Tsuyoshi

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 207 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199604)22:4<305::aid-jgt4>3.0.co;2-t

No coin nor oath required. For personal study only.

✦ Synopsis

Let G and K be connected graphs such that I GI = nlKl (n 2 2) and let p be a fixed integer satisfying 1 < p < n. We prove that if G \ A has a K-factor for every connected subgraph A with IAl = plKI, then G also has a K-factor.

📜 SIMILAR VOLUMES

Induced subgraphs and well-quasi-orderin

Induced subgraphs and well-quasi-ordering

✍ Peter Damaschke 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB

## Abstract We study classes of finite, simple, undirected graphs that are (1) lower ideals (or hereditary) in the partial order of graphs by the induced subgraph relation ≤~i~, and (2) well‐quasi‐ordered (WQO) by this relation. The main result shows that the class of cographs (__P~4~__‐free graphs

Line Graphs and Forbidden Induced Subgra

Line Graphs and Forbidden Induced Subgraphs

✍ Hong-Jian Lai; Ľubomı&#x0301;r Šoltés 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 242 KB

Beineke and Robertson independently characterized line graphs in terms of nine forbidden induced subgraphs. In 1994, S8 olte s gave another characterization, which reduces the number of forbidden induced subgraphs to seven, with only five exceptional cases. A graph is said to be a dumbbell if it con

Induced subgraphs of prescribed size

✍ Noga Alon; Michael Krivelevich; Benny Sudakov 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A subgraph of a graph __G__ is called __trivial__ if it is either a clique or an independent set. Let __q(G)__ denote the maximum number of vertices in a trivial subgraph of __G__. Motivated by an open problem of Erdős and McKay we show that every graph __G__ on __n__ vertices for which

Bipartite induced subgraphs and well-qua

Bipartite induced subgraphs and well-quasi-ordering

✍ Nicholas Korpelainen; Vadim V. Lozin 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

We study bipartite graphs partially ordered by the induced subgraph relation. Our goal is to distinguish classes of bipartite graphs that are or are not well-quasi-ordered (wqo) by this relation. Answering an open question from [J Graph Theory 16 (1992), 489-502], we prove that P 7 -free bipartite g

On induced subgraphs of a block

✍ Ladislav Nebeský 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 271 KB

If G is a block, then a vertex u of G is called critical if Gu is not a block. In this article, relationships between the localization of critical vertices and the localization of vertices of relatively small degrees (especially, of degree two) are studied. A block is called semicritical if a) each

Forbidden subgraphs and the existence of

Forbidden subgraphs and the existence of a 2-factor

✍ R. E. L. Aldred; Jun Fujisawa; Akira Saito 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB 👁 1 views

## Abstract In this paper, we consider forbidden subgraphs which force the existence of a 2‐factor. Let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}$\end{document} be the class of connected graphs of minimum degree at least two and maximum degree at least three, an