{"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","summary":"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₂.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-14","reactions":{},"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"}]}