| Home |
| About |
| Submission |
| Updating Entries |
| Using Entries |
| Search |
| Statistics |
| Index |
| Download |
A Probabilistic Proof of the Girth-Chromatic Number Theorem
| Title: | A Probabilistic Proof of the Girth-Chromatic Number Theorem |
| Author: | Lars Noschinski |
| Submission date: | 2012-02-06 |
| Abstract: | 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. |
| BibTeX: |
@article{Girth_Chromatic-AFP,
author = {Lars Noschinski},
title = {A Probabilistic Proof of the Girth-Chromatic Number Theorem},
journal = {Archive of Formal Proofs},
month = feb,
year = 2012,
note = {\url{http://isa-afp.org/entries/Girth_Chromatic.html},
Formal proof development},
ISSN = {2150-914x},
}
|
| License: | BSD License |
| Used by: | Random_Graph_Subgraph_Threshold |
| Status: [ok] | This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations. |
|
Proof outline Proof document |
| Browse theories |
| Download this entry |