✦ LIBER ✦

Girth of sparse graphs

✍ Scribed by Béla Bollobás; Endre Szemerédi

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 73 KB
Volume: 39
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10023

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For each fixed k ≥ 0, we give an upper bound for the girth of a graph of order n and size n + k. This bound is likely to be essentially best possible as n → ∞. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 194–200, 2002; DOI 10.1002/jgt.10023

📜 SIMILAR VOLUMES

Star coloring of sparse graphs

✍ Yuehua Bu; Daniel W. Cranston; Mickaël Montassier; André Raspaud; Weifan Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract A proper coloring of the vertices of a graph is called a __star coloring__ if the union of every two color classes induces a star forest. The star chromatic number χ~__s__~(__G__) is the smallest number of colors required to obtain a star coloring of __G__. In this paper, we study the r

Bisecting sparse random graphs

✍ Malwina J. Luczak; Colin McDiarmid 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB 👁 1 views

Sparse Anti-Ramsey Graphs

✍ Y. Kohayakawa; T. Luczak 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 269 KB

It is shown that for every \(l \geqslant 3\) there exists a graph \(G\) of girth / such that in any proper edge-colouring of \(G\) one may find a cycle of length / all of whose edges are given different colours. 1995 Academic Press. Inc.

On 3-Transitive Graphs of Girth 6

✍ K. Ching 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 313 KB

Graphs of Prescribed Girth and Bi-Degree

✍ Z. Furedi; F. Lazebnik; A. Seress; V.A. Ustimenko; A.J. Woldar 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 426 KB

Topological Minors in Graphs of Large Gi

Topological Minors in Graphs of Large Girth

✍ Daniela Kühn; Deryk Osthus 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 204 KB

We prove that every graph of minimum degree at least r and girth at least 186 contains a subdivision of K rþ1 and that for r5435 a girth of at least 15 suffices. This implies that the conjecture of Haj ! o os that every graph of chromatic number at least r contains a subdivision of K r (which is fal