Chromatic number

The chromatic number (also knot color number or color number for short , rarely also called color number ) of a graph is the smallest number for which the graph has a permissible knot coloration with colors. (A coloring is called admissible or valid if there are no neighboring nodes that are colored with the same color.) The chromatic number is also the smallest natural number λ for which the chromatic polynomial is. ${\displaystyle \chi (G)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \chi (G,\lambda )\neq 0}$

The achromatic number of a graph is the largest number for which it has valid and complete vertex coloring with colors. (A coloring is called complete if there is an edge for each pair of different colors, the end nodes of which are colored with these two colors.) ${\displaystyle \psi (G)}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$

The pseudo-achromatic number of a graph is the largest number for which it has a complete vertex coloring. In contrast to the achromatic number, the validity of the coloring is not required here. ${\displaystyle \psi _{s}(G)}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$

See also

• Chromatic index (edge ​​color number)