1
$\begingroup$

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:

  1. 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
  2. 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$

$\endgroup$
  • $\begingroup$ What is the chromatic number of $K_{n,n}$? What is the colouring number of $K_{n,n}$? (Hint: no matter how you order the vertices, some vertex will come last.) Yes, you can always order the vertices so that the greedy algorithm gives you an optimal colouring. If you know the colouring, list all the vertices of colour $1$ first, all the vertices of colour $2$ next, and so on. What's your point? How do you get to "therefore"? $\endgroup$ – bof Jan 16 '18 at 11:01
  • $\begingroup$ $K_{n,n}$ has $2$ as chromatic number and by ordering them in a correct way, the greedy algorithm will give me a colouring with $2$ colours. (I think so anyway). I edited my question for it to be a bit clearer. $\endgroup$ – tomak Jan 16 '18 at 11:09
  • $\begingroup$ What is your definition of the colouring number? Maybe it would help if you edited that into your definition. According to the definition I'm familiar with, the colouring number of $K_{n,n}$ is $n+1.$ Yes, you can order the vertices of $K_{n,n}$ so that the greedy algorithm uses just two colours. Yes, every graph can be ordered so that the greedy algorithm produces an optimal colouring, so what? $\endgroup$ – bof Jan 16 '18 at 11:12
  • $\begingroup$ If a graph $G$ has colouring number $k$ then $G$ is $k$-choosable, a.k.a. $k$-list-colourable. The graph $K_{3,3}$ is 2-colourable but it is not $2$-choosable. $\endgroup$ – bof Jan 16 '18 at 11:17
  • $\begingroup$ What makes you think that, if you cn order the vertices of $G$ so that the greedy algorithm gives you a $k$-colouring, then the colouring number of $G$ is at most $k$? $\endgroup$ – bof Jan 16 '18 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.