Coloring triangle-free graphs with fixed size (Q1567684)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Coloring triangle-free graphs with fixed size |
scientific article |
Statements
Coloring triangle-free graphs with fixed size (English)
0 references
19 November 2000
0 references
The authors show that if \(G\) is a triangle-free graph having \(e\) edges, then there is a constant \(c\) so that the chromatic number of \(G\) is at most \(ce^{1/3}(\log e)^{-2/3}\); then if \(G\) is a triangle-free graph of genus \(g\), there is a constant \(c\) so that the chromatic number of \(G\) is at most \(cg^{1/3}(\log g)^{-2/3}\). The latter result slightly improves the authors' previous bound [Trans. Am. Math. Soc. 349, No. 11, 4555-4564 (1997; Zbl 0884.05039)]. Both bounds are best possible, up to a constant multiple.
0 references
triangle-free graph
0 references
chromatic number
0 references
genus
0 references