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