If $X$ is a non-empty set, we say that $M\subseteq X$ is a *majority* if $|M| > |X\setminus M|$.


Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N(v)=\{x\in V: \{x,v\} \in E\}$.


Let $n$ be a positive integer. We say that a map $c:V(G) \to \{1,\ldots,n\}$ is a *majority coloring* if the following condition is satisfied:



> 
> For every $v\in V(G)$ with $N(v)\neq \emptyset$, if for some $k\in \{1,\ldots, n\}$ we have that $c^{-1}(\{k\}) \cap N(v)$ is a majority of $N(v)$, then $c(v) \neq k$.
> 
> 
> 


We set the *majority coloring number* $\chi\_{\text{m}}(G)$ to be the least positive integer $j$ such that there is a majority coloring $c:V(G)\to \{1,\ldots,j\}$.


**Question**: For every $n\in \mathbb{N}$ are there graphs with majority coloring number $n$?


I would also be grateful for hints of terminology: have majority colorings be studied anywhere, and what is the proper name?



Majority colorings
I’m basing my answer on [this MSE answer](https://math.stackexchange.com/questions/24083/graph-coloring-problem-possibly-related-to-partitions) to a similar question.


Theorem: Let $G$ be a simple graph. If $G$ has no edges, $\chi\_\mbox{maj}(G)=1$; otherwise, $\chi\_\mbox{maj}(G)=2$. 


Proof: The no-edge case is trivial: Use the coloring $c(v)=1$. Now let $G$ be a graph with at least one edge, and let $c\_0:V(G)\to\{1,2\}$ be any coloring of $G$. If $c\_0$ is a majority coloring, we are done. If not, there is a vertex $v\_0\in V(G)$ that has the same color as more than half its neighbors. Change the color of $v\_0$, and call the new coloring $c\_1$. 


If $c\_1$ is a majority coloring, we are done. If not, continue as before. Choose a vertex $v\_1$ with the same color as more than half its neighbors and recolor it to obtain a new coloring $c\_2$. And so on.


If this recoloring process reaches a majority coloring $c\_M$, $G$ is majority-colorable with two colors, so it suffices to show that this recoloring process ends. Note that at each recoloring step, exactly one vertex changes color: $c\_j(v)<>c\_{j+1}(v)$ if and only if $v<>v\_j$.


For each coloring $c\_i$, consider the number $e\_i$ of edges of $G$ that connect same-colored vertices. The recoloring process ends because $e\_i$ is a strictly decreasing sequence of nonnegative integers.


Before vertex $v\_i$ is recolored, more than half its $|N(v\_i)|$ incident edges contribute to $e\_i$. After $v\_i$ is recolored, none of these do. New edges (but only those incident to $v\_i$, since no other vertex was recolored) may contribute to $e\_{i+1}$, but they number at most half of $|N(v\_i)|$. 


