We say that a graph $G=(V,E)$ has a $k$-coloring if each vertex can be assigned a color in $\{1,…,k\}$ so that no edge has two vertices of the same color. Then, am I right in saying that if a graph is $k$-colorable, it is $(k+1)$ colorable? That is, you just don't use the color $k+1$? Or do you have to use all $k+1$ colors? Is there a difference between a graph having a coloring, and being colorable? I'm just a little confused and need some help making sense of/unraveling all these definitions.
[Math] Difference between k-coloring and k-colorable
coloringcombinatoricsgraph theory
Related Question
- 4 color theorem equivalent to cubic planar bridgeless are 3 edge colorable
- NP-completeness of chromatic sum in list coloring problem with capacity constraints
- Find all proper coloring of paths, cycles and wheels if a fix number of color in allowed
- Generalization of (vertex) coloring of a graph to hypergraphs
Best Answer
(writing for future readers)
You are right. If a graph has a $k$-coloring then it is also a $(k+1)$-coloring (which does not use colour $k+1$).
(There is a minor technical difficulty here regarding range of the coloring if we define colouring as a function; but this is not important)
A graph is said to be $k$-colourable if it has a colouring.