✦ LIBER ✦

Extremal graphs without three-cycles or four-cycles

✍ Scribed by David K. Garnick; Y. H. Harris Kwong; Felix Lazebnik

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 594 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170511

No coin nor oath required. For personal study only.

✦ Synopsis

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, Inc.

📜 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.

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.

Subthrackleable graphs and four cycles

✍ B.L. Piazza; R.D. Ringeisen; S.K. Stueckle 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 645 KB

Choosability of toroidal graphs without

Choosability of toroidal graphs without short cycles

✍ Leizhen Cai; Weifan Wang; Xuding Zhu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 1 views

## Abstract Let __G__ be a toroidal graph without cycles of a fixed length __k__, and χ~__l__~(__G__) the list chromatic number of __G__. We establish tight upper bounds of χ~__l__~(__G__) for the following values of __k__: © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 1–15, 2010.

Coloring Graphs without Short Non-boundi

Coloring Graphs without Short Non-bounding Cycles

✍ S. Fisk; B. Mohar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 357 KB

It is shown that there is a constant \(c\) such that if \(G\) is a graph embedded in a surface of genus \(g\) (either orientable or non-orientable) and the length of a shortest non-bounding cycle of \(G\) is at least \(c \log (g+1)\), then \(G\) is six-colorable. A similar result holds for three- an

Planar Graphs Without Cycles of Specific

Planar Graphs Without Cycles of Specific Lengths

✍ G. Fijavž; M. Juvan; B. Mohar; R. Škrekovski 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 208 KB

It is easy to see that planar graphs without 3-cycles are 3-degenerate. Recently, it was proved that planar graphs without 5-cycles are also 3-degenerate. In this paper it is shown, more surprisingly, that the same holds for planar graphs without 6-cycles.