Triangle-free four-chromatic graphs
type: Item
instance of: scholarly article
title: Triangle-free four-chromatic graphs
zbMATH Open document ID: 0841.05030
DOI: 10.1016/0012-365X(94)00063-O
author: Guoping Jin
published in: Discrete Mathematics
publication date: 1996-07-14T00:00:00Z
review text: Given natural numbers \(r\) and \(t\), let \(n(r, t)\) be the minimum order of a \(K^r\)-free graph \(G\) with chromatic number \(\chi(G)\geq t\). Let \[ \psi(n, K^r, t)= \max\{\delta(G)\mid K^r\subset G,\;\chi(G)\geq t,\;|G|= n\geq n(r, t)\}. \] \textit{R. Häggkvist} [Ann. Discrete Math. 13, 89-99 (1982; Zbl 0492.05047)] proved that \[ \psi(n, K^3, 4)\geq {10\over 29} n\quad\text{if} \quad 29|n. \] A nice example led Häggkvist to conjecture that \[ \psi(n, K^3, 4)= {10\over 29} n\quad\text{if} \quad 29|n. \] The main result of this paper is Theorem 9: For \(n\geq 11\), \[ \psi(n, K^3, 4)= \begin{cases} {10(n- 3)\over 29}\quad & \text{if } 29|(n- 3)\text{ and } n\geq 33\\ \lfloor{10n\over 29}\rfloor\quad & \text{otherwise}.\end{cases} \] Häggkvist's conjecture follows from Theorem 9. The author also published the paper [Comb. Probab. Comput. 2, No. 4, 479-490 (1993; Zbl 0792.05078)] studying the structure of \(K^3\)-free graphs \(G\) of order \(n\) with \(\delta(G)> {10n\over 29}\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 810262
zbMATH Keywords: chromatic number
zbMATH Keywords: Häggkvist's conjecture
reviewed by: H. P. Yap
MaRDI profile type: Publication
cites work: On the connection between chromatic number, maximal clique and minimal degree of a graph
cites work: Q4830805
cites work: Q3996285
cites work: On a valence problem in extremal graph theory
cites work: ODD Cycles of Specified Length in Non-Bipartite Graphs
cites work: Q5781249
description: scientific article; zbMATH DE number 810262