A Probabilistic Proof of the Girth-Chromatic Number Theorem. 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.

References in zbMATH (referenced in 1 article , 1 standard article )

Showing result 1 of 1.
Sorted by year (citations)

  1. Noschinski, Lars: Proof pearl: a probabilistic proof for the girth-chromatic number theorem (2012)