𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subthrackleable graphs and four cycles

✍ Scribed by B.L. Piazza; R.D. Ringeisen; S.K. Stueckle

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
645 KB
Volume
127
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Graphs without four-cycles
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

Four-cycles in graphs without a given ev
Four-cycles in graphs without a given even cycle
✍ Daniela KΓΌhn; Deryk Osthus πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 104 KB

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.

Random Ramsey graphs for the four-cycle
Random Ramsey graphs for the four-cycle
✍ ZoltΓ‘n FΓΌredi πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 223 KB

It is shown that there is a graph 4 with n vertices and at least n ' "edges such that it contains neither Ws nor X2 3 , but every subgraph with 2n4'3(logn)Z edges contains a vd, (n>n,). Moreover, the chromatic number of Y is at least no.'.