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 source
  • chromatic number upper bounds maximum clique by a linear function – Unbounded clique implies the number of needed colors is unbounded.
  • degeneracy upper bounds chromatic number by a linear function – 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 upper bounds chromatic number by a linear function – Removed vertices get one color each and we need only $2$ colors for the rest.
• chordality1993
  • page 2 : chromatic number upper bounds chordality by a linear function – Corollary 4. For any graph $G$, $\mathrm{Chord}(G) \le \chi(G)$, the chromatic number of $G$.