Delphi.science

Erdős Problem 1111: Wagon's bound

Source: github.com/VictorLiwentao/fc-palomar-proofs/tree/6d83e8abde…

Wentao Li

Palomar Registrypalomar/PALOMAR-2026-11-14-000024Nov 14, 2026math.COscore 0

Every finite graph with no clique of size t and chromatic number at least C(t,2)+1 has two anticomplete vertex sets that each induce a graph of chromatic number at least 2 (Wagon 1980, as noted by El-Zahar and Erdős). In Erdős Problem 1111, d(t,c) is the least d such that every finite graph with clique number less than t and chromatic number at least d has two anticomplete vertex sets A, B with χ(G[A]) ≥ c and χ(G[B]) ≥ c (El-Zahar and Erdős 1985). So the result says d(t,2) ≤ C(t,2)+1. Two anticomplete sets that each induce a graph of chromatic number at least 2 are the same as an induced 2K₂.

RepositoryJSONText

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-11-14-000024
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-14-000024/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-11-14-000024/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'