The following concept arose when studying some properties of a real world computer network.


Let $G=(V,E)$ be a finite, simple, undirected graph. If $v\in V$ we set $N(v)=\{y\in V:\{v,y\}\in E\}$. Let $Z\neq \emptyset$ be a set. A map $c:V\to Z$ is said to be an "almost coloring" of $G$ if for all $v\in V$ the color of $v$ appears at most once in $N(v)$, that is, mathematically speaking, if $$|c^{-1}(\{c(v)\})\cap N(v)| \leq 1.$$ Let $\chi\_a(G)$ denote the smallest integer $n$ such that there is an almost coloring $c:V\to\{1,\ldots,n\}$.


**Question**. If $G,H$ are finite, simple, undirected graphs with $\chi(G)\le \chi(H)$, does this imply that $\chi\_a(G)\le\chi\_a(H)$?




---


Also, I would be very grateful for a reference in case this concept that I call almost coloring has been studied elsewhere.



"Almost" vertex coloring
No for $G=K\_{2,1}$ (two edges with common vertex) and $H=K\_{1,1}$ (an edge). Both chromatic numbers are equal to 1, and almost chromatic numbers are 2 and 1 respectively.


