✦ LIBER ✦

On independent generalized degrees and independence numbers in K(1, m)-free graphs

✍ Scribed by R.J. Faudree; R.J. Gould; M.S. Jacobson; L.M. Lesniak; T.E. Lindquester

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 427 KB
Volume: 103
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90035-e

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the independence number in K1, r+1-fr

On the independence number in K1, r+1-free graphs

✍ Zdeněk Ryjáček; Ingo Schiermeyer 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 353 KB

In this paper we use the degree sequence, order, size and vertex connectivity of a K 1,,+ 1 -free graph or of an almost claw-free graph to obtain several upper bounds on its independence number. We also discuss the sharpness of these results.

Degree sequence and independence in K(4)

Degree sequence and independence in K(4)-free graphs

✍ Paul Erdős; Ralph Faudree; Talmage James Reid; Richard Schelp; William Staton 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 268 KB

We investigate whether K,-free graphs with few repetitions in the degree sequence may have independence number o(n). We settle the cases r = 3 and r >/5, and give partial results for the very interesting case r=4. In an earlier article I-4] it is shown that triangle-free graphs in which no term of

Degree multiplicities and independent se

Degree multiplicities and independent sets in K4-free graphs

✍ Béla Bollobás 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 555 KB

Independent Arithmetic Progressions in C

Independent Arithmetic Progressions in Clique-Free Graphs on the Natural Numbers

✍ David S. Gunderson; Imre Leader; Hans Jürgen Prömel; Vojtěch Rödl 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 179 KB

We show that if G is a K r -free graph on N, there is an independent set in G which contains an arbitrarily long arithmetic progression together with its difference. This is a common generalization of theorems of Schur, van der Waerden, and Ramsey. We also discuss various related questions regarding

Size and independence in triangle-free g

Size and independence in triangle-free graphs with maximum degree three

✍ Kathryn Fraughnaugh Jones 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 549 KB

## Abstract Let __C__ be the class of triangle‐free graphs with maximum degree at most three. A lower bound for the number of edges in a graph of __C__ is derived in terms of the number of vertices and the independence. Several classes of graphs for which this bound is attained are given. As coroll

Edge density and independence ratio in t

Edge density and independence ratio in triangle-free graphs with maximum degree three

✍ Jerrold Griggs; Owen Murphy 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 548 KB

A simple polynomial-time algorithm is presented which computes independent sets of guaranteed size in connected triangle-free noncubic graphs with maximum degree 3. Let nand m denote the number of vertices and edges, respectively, and let c '= m/n denote the edge density where c < 3/2. The algorithm