✦ LIBER ✦

Four-cycles in graphs without a given even cycle

✍ Scribed by Daniela Kühn; Deryk Osthus

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 104 KB
Volume: 48
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20048

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that every bipartite C 2' -free graph G contains a C 4free subgraph H with e(H) ! e(G)=(' À 1). The factor 1=(' À 1) is best possible. This implies that ex(n; C 2' ) 2(' À 1)ex(n; fC 4 ; C 2' g), which settles a special case of a conjecture of Erdo ˝s and Simonovits.

📜 SIMILAR VOLUMES

Graphs without four-cycles

✍ C. R. J. Clapham; A. Flockhart; J. Sheehan 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 722 KB

We investigate the values of t(n), the maximum number of edges in a graph with n vertices and not containing a four-cycle. Techniques for finding these are developed and the values of t(n) for all n up to 21 are obtained. All the corresponding extremal graphs are found.

Extremal graphs without three-cycles or

Extremal graphs without three-cycles or four-cycles

✍ David K. Garnick; Y. H. Harris Kwong; Felix Lazebnik 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 594 KB

## Abstract We derive bounds for __f(v)__, the maximum number of edges in a graph on __v__ vertices that contains neither three‐cycles nor four‐cycles. Also, we give the exact value of __f(v)__ for all __v__ up to 24 and constructive lower bounds for all __v__ up to 200. © 1993 John Wiley & Sons, I

Even cycles in graphs

✍ Joseph G. Conlon 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 888 KB

## Abstract Let __G__ be a 3‐connected simple graph of minimum degree 4 on at least six vertices. The author proves the existence of an even cycle __C__ in __G__ such that __G‐V__(__C__) is connected and __G‐E__(__C__) is 2‐connected. The result is related to previous results of Jackson, and Thomas

Nonseparable graphs with a given number

Nonseparable graphs with a given number of cycles

✍ Ranko Šćepanović; Gerhard Ringel; Dragan Marušič; G. L. Chia; Brian Alspach 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 646 KB

## Abstract G. Ringel conjectured that for every positive integer __n__ other than 2, 4, 5, 8, 9, and 16, there exists a nonseparable graph with __n__ cycles. It is proved here that the conjecture is true even with the restriction to planar and hamiltonian graphs.

Covering a graph with cycles passing thr

Covering a graph with cycles passing through given edges

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 91 KB 👁 2 views

We propose a conjecture: for each integer k ≥ 2, there exists N (k) such that if G is a graph of order n ≥ N (k) and d(x) + d(y) ≥ n + 2k -2 for each pair of nonadjacent vertices x and y of G, then for any k independent edges e 1 , . . . , e k of G, there exist If this conjecture is true, the condi

Even cycles with prescribed chords in pl

Even cycles with prescribed chords in planar cubic graphs

✍ Herbert Fleischner 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 254 KB

The following result is being proved. Theorem: Let e be an arbitrary line of the 2-connected, 3-regular, planar graph G such that e cioes not belong to any cut set of size 2. Then G contains an even cycle for which e is a chord.