Existence of Graphs with High Girth and High Chromatic Number

Name: Existence of Graphs with High Girth and High Chromatic Number
Uploaded: 2024-11-06T17:36:21Z
Duration: 25 min 19 s
Description: Application of the probabilistic method in combinatorics to graph theory. Proof of a classic and ingenious result of Erdős that there exists a graph with arbitrarily high girth and chromatic number.

25:19

Application of the probabilistic method in combinatorics to graph theory. Proof of a classic and ingenious result of Erdős that there exists a graph with arbitrarily high girth and chromatic number.