# Upper bound on chromatic number

Suppose I have a graph $G$ and a function $f:V(G) \to \mathbb{N}$ so that for all $v\in V(G)$ we have:

$$| \{f(v)-f(w)\ge 0 \mid w \in N(v)\} | \le k.$$

Show that the chromatic number $\chi (G) \le k+1$.

I think we can solve this algorithmically; choose the largest numbered vertex $v\in G$ and note that $v$ must have degree at most $k$, so we can color $v$ and its neighbors different colors. I cannot figure out how to continue the algorithm though.

It's just the greedy algorithm, right? The details should be something like this: order the vertices using $f$, from largest to smallest, say $v_1 \cdots v_n$. Go through the vertices, coloring $v_i$ with the smallest color not already used by his neighbors. Now, the only neighbors of his already colored have at least as large $f$ value, since we are visiting vertices in decreasing $f$ value. Since there are at maximum $k$ of those, his color will be at maximum $k+1$. This gives the bound on $\chi(G)$.