# “Almost” vertex coloring

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.

• No, take $G=K_{2,1}$, $H=K_{1,1}$. – Fedor Petrov Jul 21 '17 at 13:18
• @FedorPetrov is right, but he has $G$ and $H$ mixed up. What he was pointing out is that $\chi(K_{1,1}) = \chi(K_{2,1})$, but $\chi_a(K_{1,1}) < \chi_a(K_{2,1})$. – Tobias Fritz Jul 21 '17 at 14:47
• @PeterHeinig I think, $\chi_a(K_{21})=2$, is not it? – Fedor Petrov Jul 21 '17 at 15:28
• @TobiasFritz I think, I did not even mix them up:) – Fedor Petrov Jul 21 '17 at 17:59
• @DominicvanderZypen: in case you really need to know as much as possible about "coloring with defect 1" (as David Wood correctly pointed out it is called), let me mention a relevant reference so new that it is not yet available: the is a talk on the subject coming up: David Wood of Monash University, Tutorial on defective and clustered graph colouring, scheduled for Monday August 21 between 09:00 and 10:00 MDT – Peter Heinig Aug 17 '17 at 10:57

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.
This is called a "colouring with defect 1". If each vertex is adjacent to at most $d$ vertices of the same colour, then it is a colouring with defect $d$. There is a huge literature on this topic; see https://en.wikipedia.org/wiki/Defective_coloring.