For graph G and integer k, exist coloring $V\to [k]$ s.t. $(1-1/k)$ of every vertex get different color.

Question

For any simple graph $G$ and positive integer $k$, there exists a coloring $c: V(G) \rightarrow[k]$ such that for every vertex $v$ of $G,$ at least $(1-1/k)$-fraction of its neighbors get different colors.

I am studying extremal combinatorics, and this is a conclusion in the textbook. I cann't find its proof or figure it out by myself. Can someone help me?

Answer 1

This is an extension of a well-known result about largest bipartite subgraphs.

Choose a $k$-coloring of the vertices of $G$ such that the number of edges with different colors is maximized. Then this coloring will have the property you want.

For any vertex $v$, the color of $v$ must be the least popular color in $N(v)$ (otherwise, we could change $v$'s color to the least popular color, and increase the number of edges with different colors on the endpoints). Therefore the color of $v$ is used on at most $\frac1k|N(v)|$ of its neighbors - at least a $(1 - \frac1k)$ fraction of $v$'s neighbors have a color different from $v$'s.