Zulip Chat Archive
Stream: graph theory
Topic: Coloring odd loops / components
John Talbot (May 01 2025 at 16:04):
Is this in Mathlib?
G.Colorable 2 ↔ ∀ u, ∀ (w : G.Walk u u), ¬ Odd w.length
I can see Walk.three_le_chromaticNumber_of_odd_loop
but the other direction would seem to require something like
G.Colorable n ↔ ∀ c : G.ConnectedComponent, (G.induce c).Colorable n
which I also can't see.
Am I missing something obvious? (If not I'd be happy to add these.)
Last updated: May 02 2025 at 03:31 UTC