Can I read Almost All Graphs with High Girth and Suitable Density Have High Chromatic Number on EtoBox?

Almost All Graphs with High Girth and Suitable Density Have High Chromatic Number by Deryk Osthus; Hans Jürgen Prömel; Anusch Taraz is a Computer Science article available to read on EtoBox.

What is Almost All Graphs with High Girth and Suitable Density Have High Chromatic Number about?

## Abstract Erdös proved that there exist graphs of arbitrarily high girth and arbitrarily high chromatic number. We give a different proof (but also using the probabilistic method) that also yields the following result on the typical asymptotic structure of graphs of high girth: for all l ≥ 3 and __k__ ∈ N there exist constants __C__~1~ and __C__~2~ so that almost all graphs on __n__ vertices and __m__ edges whose girth is greater than l have chromatic number at least __k__, provided that $C\_{1}n\,\leq\, m\,\leq\, C\_{2}n^{\ell /(\ell -1)}$. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 220–226, 2001

Who reads Almost All Graphs with High Girth and Suitable Density Have High Chromatic Number?

Author

Deryk Osthus; Hans Jürgen Prömel; Anusch Taraz

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 0364-9024)

Published

2001

Language

EN

Field

Computer Science (Physical Sciences)