✦ LIBER ✦

Degree multiplicities and independent sets in K4-free graphs

✍ Scribed by Béla Bollobás

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 555 KB
Volume: 158
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00002-e

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

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

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

Maximal independent sets in bipartite gr

Maximal independent sets in bipartite graphs

✍ Jiuqiang Liu 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB 👁 1 views

## Abstract A maximal independent set of a graph __G__ is an independent set that is not contained properly in any other independent set of __G.__ In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order __n__ and the extremal graphs as well as

Independent sets in random sparse graphs

✍ Pedro G. Gazmuri 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 418 KB

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