Graph coloring: $G$ is a graph where the number of vertices with degree of at least $k$, is at most $k$. Prove $χ(G) \le k$

Question

$G$ is a graph where the number of vertices with a degree of at least $k$, is at most $k$.

Prove: $χ(G) \le k$

I'm trying to look at the $K_k$ clique and this proves that $χ(G) \ge k$ but I don't see how to go on from there with the $n-k$ vertices.

Any hints or directions would be appreciated.

Answer 1

First assign each of the colours $1,...,k$ to each of the (at most) $k$ vertices with degree $\geq k$ (i.e. assign a different colour to each vertex). Now, the uncoloured vertices which remain in $G$ each have degree at most $k-1$. Colour each vertex in turn. Whenever you reach a vertex, its neighbourhood can contain at most $k-1$ colours, so there is always a colour among colours $1,...,k$ leftover for this vertex.