Email Gateway (Aug 18 2022 at 19:05): Email Gateway (Aug 18 2022 at 19:05):From: Tobias Nipkow <nipkow@in.tum.de>
A Probabilistic Proof of the Girth-Chromatic Number Theorem
Lars Noschinski
This works presents a formalization of the Girth-Chromatic number
theorem in graph theory, stating that graphs with arbitrarily large
girth and chromatic number exist. The proof uses the theory of Random
Graphs to prove the existence with probabilistic arguments.
http://afp.sourceforge.net/entries/Girth_Chromatic.shtml
Enjoy!
Last updated: Apr 18 2024 at 20:16 UTC