Open Research Index

Triangle-free graphs with prescribed chromatic number

alexander

Palomar Registrypalomar/PALOMAR-2026-10-14-000006Oct 14, 2026math.COscore 0

A Lean formalization of the classical existence of finite triangle-free graphs with arbitrarily large chromatic number. For each integer k at least two, it constructs a finite simple graph whose clique number is exactly two and whose chromatic number is exactly k. The proof iterates the Mycielski construction from the complete graph on two vertices. This is the Tutte–Zykov variant recorded with Erdős problem 627, not a solution of that problem's open asymptotic limit question.

SourceRepositoryJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-10-14-000006
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-14-000006/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-14-000006/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'