𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The chvátal-erdo˝s condition for cycles in triangle-free graphs

✍ Scribed by Dingjun Lou

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
235 KB
Volume
152
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved that if G is a triangle-free graph with v vertices whose independence number does not exceed its connectivity then G has cycles of every length n for 4: /2 or G is a 5-cyde. This was conjectured by Amar, Fournier and Germa.

All graphs considered are finite, undirected and simple. A graph G of order v is said to be pancyclic if for every n(3 ~n ~v) there is a cycle C n of length n in G. Similarly, G is vertex pancyclic if for every vertex v and every n there is a cycle C n containing v.

Let C be a cycle of G. We always assume that C has an orientation which is

📜 SIMILAR VOLUMES

Chvátal-Erdős conditions for pat
Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
✍ Bill Jackson; Oscar Ordaz 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 783 KB

We give a survey of results and conjectures concerning sufficient conditions in terms of connectivity and independence number for which a graph or digraph has various path or cyclic properties, for example hamilton path/cycle, hamilton connected, pancyclic, path/cycle covers, 2-cyclic.