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) $.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.