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.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ No, take $G=K_{2,1}$, $H=K_{1,1}$. $\endgroup$
    – Fedor Petrov
    Commented Jul 21, 2017 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
    Commented Jul 21, 2017 at 14:47
  • 1
    $\begingroup$ @PeterHeinig I think, $\chi_a(K_{21})=2$, is not it? $\endgroup$
    – Fedor Petrov
    Commented Jul 21, 2017 at 15:28
  • 1
    $\begingroup$ @TobiasFritz I think, I did not even mix them up:) $\endgroup$
    – Fedor Petrov
    Commented Jul 21, 2017 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
    Commented Aug 17, 2017 at 10:57

2 Answers 2

Reset to default
2
$\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.

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .