Id: palomar/PALOMAR-2026-11-14-000024 Url: https://github.com/VictorLiwentao/fc-palomar-proofs/tree/6d83e8abde581b91eb1dde2b397136c5d218db64 Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-14-000024-v1.json Repo: https://github.com/VictorLiwentao/fc-palomar-proofs Tags: math.CO, msc:05C15, msc:05C69 Score: 0 Title: Erdős Problem 1111: Wagon's bound Trust: high Domain: math.CO Source: palomar Authors: Wentao Li Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-14 Formalized: true Formalizes: title=A bound on the chromatic number of graphs without certain induced subgraphs identifier=doi:10.1016/0095-8956(80)90093-3 relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-14-000024 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₂.