I would like to understand the difference between the chromatic number and the colouring number. I get definition of both but it seems to me that they will have the same values for any graph.
Def:
- The chromatic number is the minimal number of colours necessary to colour a graph such that no two vertices of the same colour are adjacent
- The colouring number of $G$ is $$\underset{L}{\text{min}} \underset{v\in V(G)}{\text{max}} \#\text{ left neighbours of $v$ in $L$} + 1$$ where $L$ is an ordering of the vertices
Suppose a graph $G$ has a chromatic number $k$ then it seems that you can always order the vertices such that the greedy algorithm will exactly give you a $k$-colouring. therefore the colouring number will also be exactly $k$