Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a graph with chromatic number . Must there exist an edge such that, for all large , contains a cycle of length containing ?
Source: erdosproblems.com/737
An accepted solution exists. The statement is true.
Proved: the site labels the problem PROVED and credits Thomassen [Th83], whose theorem gives, in any graph of uncountable chromatic number, an edge lying on a cycle of every sufficiently large length. The site attributes the question to Erdős, Hajnal and Shelah [EHS74], who proved that such a graph contains odd cycles of every sufficiently large length, Problem 594.