chromatic number

• 1993 chordality1993
  • page 2 : chromatic number $k$ upper bounds chordality by $\mathcal O(k)$ – Corollary 4. For any graph $G$, $\mathrm{Chord}(G) \le \chi(G)$, the chromatic number of $G$.
• 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.