On the structure of triangle-free graphs of large minimum degree
type: Item
instance of: scholarly article
title: On the structure of triangle-free graphs of large minimum degree
zbMATH Open document ID: 1112.05055
published in: Combinatorica
publication date: 2007-01-08T00:00:00Z
review text: For all \(\varepsilon, N > 0\) Hajnal constructed triangle-free graphs \(G\) on \(n\) vertices of minimum degree at least \((1/3-\varepsilon)n\) and chromatic number at least \(N\). \textit{C. Thomassen} [Combinatorica 22, No. 4, 591--596 (2002; Zbl 1026.05042)] proved that this result is sharp: for every \(\varepsilon > 0\) there exists \(K=K(\varepsilon)\) such that the chromatic number of every triangle-free graph of minimum degree at least \((1/3+\varepsilon)n\) has chromatic number at most \(K(\varepsilon)\). The author improves this result in the following sense: for every \(\varepsilon > 0\) there exists \(L=L(\varepsilon)\) such that every triangle-free graph of minimum degree at least \((1/3+\varepsilon)n\) is homomorphic to a triangle-free graph on at most \(L\) vertices. The proof is based on the Szemerédi regularity lemma.
reviewed by: Csaba Szabó
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5082378
zbMATH Keywords: extremal problems
author: Tomasz Łuczak
MaRDI profile type: Publication
full work available at URL: s00493-006-0028-8
OpenAlex ID: W2049127787
DOI: 10.1007/S00493-006-0028-8
description: scientific article; zbMATH DE number 5082378