✦ LIBER ✦

Lower bounds on size and independence inK4-free graphs

✍ Scribed by Fraughnaugh, Kathryn L.; Locke, Stephen C.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 131 KB
Volume: 26
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199710)26:2<61::aid-jgt1>3.0.co;2-d

No coin nor oath required. For personal study only.

✦ Synopsis

We investigate lower bounds on the size of K 4 -free graphs. For several ranges of independence relative to order and for graphs with maximum degree 3 and 4, we find sharp lower bounds. We also evaluate Ramsey-type numbers over the classes of graphs with maximum degree 3 and with maximum degree 4.

📜 SIMILAR VOLUMES

Improved lower bounds on k-independence

✍ Yair Caro; Zsolt Tuza 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 418 KB

## Abstract A vertex set __Y__ in a (hyper)graph is called __k__‐independent if in the sub(hyper)‐graph induced by __Y__ every vertex is incident to less than __k__ edges. We prove a lower bound for the maximum cardinality of a __k__‐independent set—in terms of degree sequences—which strengthens an

New lower bounds for the size of edge ch

New lower bounds for the size of edge chromatic critical graphs

✍ Yue Zhao 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 1 views

## Abstract In this paper, by applying the discharging method, we obtain new lower bounds for the size of edge chromatic critical graphs for small maximum degree Δ. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 81–92, 2004

Sharp bounds on the order, size, and sta

Sharp bounds on the order, size, and stability number of graphs

✍ Pierre Hansen; Maolin Zheng 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB

## Abstract We consider graphs __G = (V,E)__ with order ρ = |__V__|, size __e__ = |__E__|, and stability number β~0~. We collect or determine upper and lower bounds on each of these parameters expressed as functions of the two others. We prove that all these bounds are sharp. © __1993 by John Wiley