0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ No, take $G=K_{2,1}$, $H=K_{1,1}$. $\endgroup$ – Fedor Petrov Jul 21 '17 at 13:18
  • 1
    $\begingroup$ @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})$. $\endgroup$ – Tobias Fritz Jul 21 '17 at 14:47
  • 1
    $\begingroup$ @PeterHeinig I think, $\chi_a(K_{21})=2$, is not it? $\endgroup$ – Fedor Petrov Jul 21 '17 at 15:28
  • 1
    $\begingroup$ @TobiasFritz I think, I did not even mix them up:) $\endgroup$ – Fedor Petrov Jul 21 '17 at 17:59
  • 1
    $\begingroup$ @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 $\endgroup$ – Peter Heinig Aug 17 '17 at 10:57
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.