Problem 57

If $G$ is a graph with infinite chromatic number and $a_1<a_2<\cdots$ are lengths of the odd cycles of $G$ then $\sum \frac{1}{a_i}=\infty$ .

Source: erdosproblems.com/57

Graph theory
Chromatic number
Cycles

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED (LEAN), crediting the solution to Liu and Montgomery; the Lean behind the qualifier is described below. The accepted claim is Liu and Montgomery's odd interval theorem.

Original problem references, as listed by the site. [ErHa66], [Er69b], [Er74d], [Er81], [Er90], [Er93, p. 342], [Er94b], [Er95], [Er95d], [Er96], [Er97b], [Va99, 3.58]. These are the site header's historical statement references. Of these, [Er97b] (Erdős, Some old and new problems in various branches of combinatorics, Discrete Math. 165/166 (1997), 227--231) is carded: item 3 on p. 228 states the conjecture, quoted on its card, Erdős 1997.

Problem 57

Status

Proof claims

Discussion