Triangle-free four-chromatic graphs (Q1901038): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q1164054 |
||
Property / reviewed by | |||
Property / reviewed by: Hian Poh Yap / rank | |||
Revision as of 08:32, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Triangle-free four-chromatic graphs |
scientific article |
Statements
Triangle-free four-chromatic graphs (English)
0 references
14 July 1996
0 references
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}\).
0 references
chromatic number
0 references
Häggkvist's conjecture
0 references