✦ LIBER ✦

Graphs omitting sums of complete graphs

✍ Scribed by Cherlin, Gregory; Shi, Niandong

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 119 KB
Volume: 24
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199703)24:3<237::aid-jgt5>3.0.co;2-q

No coin nor oath required. For personal study only.

✦ Synopsis

For every finite m and n there is a finite set {G 1 , . . . , G l } of countable (m • K n )-free graphs such that every countable (m • K n )-free graph occurs as an induced subgraph of one of the graphs G i .

📜 SIMILAR VOLUMES

Graphs omitting a bushy tree

✍ Cherlin, G.; Shi, N.; Tallgren, L. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB 👁 2 views

A tree is called bushy if it has no vertex of degree 2. Theorem: the class of countable graphs omitting a fixed finite bushy tree with at least 5 vertices has no universal element.

Graphs omitting a finite set of cycles

✍ Cherlin, Gregory; Shi, Niandong 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB 👁 2 views

We prove that for C a finite set of cycles, there is a universal C-free graph if and only if C consists precisely of all the odd cycles of order less than same specified bound.

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 1 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Complete minors in pseudorandom graphs

✍ Andrew Thomason 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB

Fan-complete graph Ramsey numbers

✍ Li, Yusheng; Rousseau, Cecil C. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB 👁 1 views

It is shown that if G and H are arbitrary fixed graphs and n is sufficiently large, then Also, we prove that r ( K 1 +F, K,) 5 (m+o(l))&(n -+ GO) for any forest Fwhose largest component has m edges. Thus r(Fe, K,) 5 (1 + o(l))&, where Fe = K1 + CK2. We conjecture that r(Fe, K,) -&(n + cm).

Degree sums for edges and cycle lengths

Degree sums for edges and cycle lengths in graphs

✍ Brandt, Stephan; Veldman, Henk Jan 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 2 views

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference-the length of a longest cycle-of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length be