Bounds for the smallest $k$-chromatic graphs of given girth
Let $n_g(k)$ denote the smallest order of a $k$-chromatic graph of girth at least $g$. We consider the problem of determining $n_g(k)$ for small values of $k$ and $g$. After giving an overview of what is known about $n_g(k)$, we provide some new lower bounds based on exhaustive searches, and then ob...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/4576/pdf |