✦ LIBER ✦

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

✍ Scribed by Zdeněk Ryjáček; Ingo Schiermeyer

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 353 KB
Volume: 138
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00218-8

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On independent generalized degrees and i

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

✍ R.J. Faudree; R.J. Gould; M.S. Jacobson; L.M. Lesniak; T.E. Lindquester 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 427 KB

A note on the independence number of tri

A note on the independence number of triangle-free graphs

✍ James B. Shearer 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 188 KB

Hamiltonicity for K1, r-free graphs

✍ Guantao Chen; R. H. Schelp 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 719 KB

## Abstract In this paper, we investigate the Hamiltonicity of __K__~1,r~‐free graphs with some degree conditions. In particular, let __G__ be a __k__‐connected grph of order __n__≧3 which is __K__~1,4~‐free. If magnified image for every independent set {__v__~0~, __v__~1~, …, __v__~k~} then __G__

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

On weights of induced paths and cycles i

On weights of induced paths and cycles in claw-free and K1,r-free graphs

✍ J. Harant; M. Voigt; S. Jendrol; B. Randerath; Z. Ryjáček; I. Schiermeyer 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 3 views

On the number of (r,r+1)- factors in an

On the number of (r,r+1)- factors in an (r,r+1)-factorization of a simple graph

✍ A. J. W. Hilton 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 113 KB 👁 1 views

## Abstract For integers __d__≥0, __s__≥0, a (__d, d__+__s__)‐__graph__ is a graph in which the degrees of all the vertices lie in the set {__d, d__+1, …, __d__+__s__}. For an integer __r__≥0, an (__r, r__+1)‐__factor__ of a graph __G__ is a spanning (__r, r__+1)‐subgraph of __G__. An (__r, r__+1)‐