Determine h_3(k): fewest vertices in a triangle-free graph of chromatic number k (Erdős #1013)
Statement
Let $h_3(k)$ be the least number $n$ of vertices such that there exists a triangle-free graph on $n$ vertices with chromatic number $k$. Find an asymptotic formula for $h_3(k)$, and prove that $$\lim_{k\to\infty}\frac{h_3(k+1)}{h_3(k)}=1.$$
Acceptance. FULLY RESOLVES: an asymptotic formula for $h_3(k)$ pinning the leading constant (currently trapped between $(\tfrac12-o(1))k^2\log k$ and $(1+o(1))k^2\log k$), AND a proof that $h_3(k+1)/h_3(k)\to 1$ — delivered as a complete proof. ADVANCES, any of: (a) extend the exact sequence A292528 by determining a new value $h_3(k)$ beyond the known $h_3(5)=22$ (i.e. $h_3(6)$), delivering (i) a triangle-free graph on $N$ vertices with chromatic number $k$ — machine-verifiable: no triangle plus a certificate that it needs $k$ colours — and (ii) an exhaustiveness certificate (e.g. a SAT UNSAT proof) that no triangle-free graph on $N-1$ vertices has chromatic number $k$; (b) improve either multiplicative constant in the bounds stated in the background, strictly better than the best bound stated above, with proof. Deliver the graph + colouring/lower-bound certificate + exhaustiveness proof, or the improved-bound proof.
Background
Posed by Erdős [Er71]. The function $h_3(k)$ is dual to the function $f(n)$ = maximum chromatic number of a triangle-free graph on $n$ vertices (erdosproblems.com/1104): $h_3(k)=n$ exactly when $n$ is minimal with $f(n)=k$. Graver and Yackel [GrYa68] proved $h_3(k)\gg \tfrac{\log k}{\log\log k}k^2$, and the modern bounds on $f(n)$ give $$\left(\tfrac12-o(1)\right)k^2\log k\leq h_3(k)\leq (1+o(1))k^2\log k;$$ the exact leading constant, and the ratio limit above, are open. The small exact values are known from computer search: $h_3(2)=2$, $h_3(3)=5$ (the $5$-cycle), $h_3(4)=11$ (the Grötzsch graph, minimality proved by Chvátal), and $h_3(5)=22$ (Jensen and Royle); $h_3(6)$ is not known. These counts form OEIS A292528, and the problem is intimately connected to the Ramsey number $R(3,k)$; see erdosproblems.com/920 for the $K_r$-free generalisation. Listed as open on erdosproblems.com/1013 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'); a companion to the extremal problem #1011. Attacker's tool: SAT / exhaustive computer search to extend the exact sequence A292528 and to build triangle-free graphs of high chromatic number, together with $R(3,k)$ bound transfer to sharpen the constant.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1013 (T. F. Bloom) | website |
| REF-02 | OEIS A292528 — least order of a triangle-free graph with chromatic number n | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.