is it possible to find a graph whose vertex chromatic number = 2010 + edge chromatic number? And how to prove it?
Thank for any advice.
[Math] Graph with vertex chromatic number greater than edge chromatic number
coloringgraph theory
coloringgraph theory
is it possible to find a graph whose vertex chromatic number = 2010 + edge chromatic number? And how to prove it?
Thank for any advice.
Best Answer
The vertex chromatic number can't exceed the edge chromatic number by more than $1$.
Let $\chi$ be the vertex chromatic number, $\chi'$ the edge chromatic number. You can get $\chi(G)=\chi'(G)+1$ by taking $G=K_{2n}$.
If $\Delta$ is the maximum degree, then $\chi(G)\le\Delta(G)+1\le\chi'(G)+1$.