By Brooks's theorem, one can take $k=n$ when the graph (assumed to be connected) is not isomorphic to $K_p$ (the complete graph on $p$ vertices), and $C_p$ (the cycle on $p$ vertices), $p$ odd.
Paul Broussous
- 6.3k
- 1
- 19
- 32