Coloring triangle-free graphs with fixed size
type: Item
instance of: scholarly article
title: Coloring triangle-free graphs with fixed size
zbMATH Open document ID: 0948.05027
DOI: 10.1016/S0012-365X(00)00087-X
author: Carsten Thomassen
author: John Gimbel
published in: Discrete Mathematics
publication date: 2000-11-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1462337
zbMATH Keywords: triangle-free graph
zbMATH Keywords: chromatic number
zbMATH Keywords: genus
Wikidata QID: Q30039999
reviewed by: Arthur T. White
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00087-x
OpenAlex ID: W2075303922
Recommended article: Colouring Vertices of Triangle-Free Graphs
Recommended article: Q4566241
Recommended article: Structure and colour in triangle-free graphs
Recommended article: Q5133058
Recommended article: Counting colorings of triangle-free graphs
Recommended article: Triangle-free graphs with large chromatic numbers
Recommended article: Coloring triangle‐free graphs with local list sizes
Recommended article: Q4525265
Recommended article: Colouring vertices of triangle-free graphs without forests
Recommended article: A Class of Three‐Colorable Triangle‐Free Graphs
description: scientific article; zbMATH DE number 1462337