Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let . If the edges of are -coloured then there exist vertices with at least one colour missing on the edges of the induced .
Source: erdosproblems.com/617
No claim settles this problem.
Falsifiable, the site's label: a counterexample would be a finite coloring for one value of and could be checked by a finite computation, while a proof for every could not. The problem is open: the cases are refereed (Erdős and Gyárfás 1999, the accepted partial claim page 1999_04_01_erdos_gyarfas, and, for , earlier by Chung and Liu 1978 (1978_01_01_chung_liu)); the fixed cases are claimed in 2026 preprints, write-ups and Lean developments recorded on the claim pages below, none refereed, and none with a review that counts as acceptance; and no proof for all and no counterexample is known (site accessed 2026-09-04; proof-claim thread with its comments and discussion thread accessed 2026-10-07). Partial claims derive nothing for the standing.