chromatic number
- https://mathworld.wolfram.com/ChromaticNumber.html
- chromatic number – The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color (Skiena 1990, p. 210), …
- unknown
- chromatic number $k$ upper bounds maximum clique by $\mathcal O(k)$ – Unbounded clique implies the number of needed colors is unbounded.
- degeneracy $k$ upper bounds chromatic number by $\mathcal O(k)$ – Greedily color the vertices in order of the degeneracy ordering. As each vertex has at most $k$ colored predecesors we use at most $k+1$ colors.
- distance to bipartite $k$ upper bounds chromatic number by $\mathcal O(k)$ – Removed vertices get one color each and we need only $2$ colors for the rest.
- chromatic number $k$ upper bounds chordality by $f(k)$