Who knows the name of the following coloring of graphs, a proper vertex coloring so that for every vertex its every two neighbors receive different colors?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Well from your original graph $G$ it's easy to make a new graph $G'$ with the same vertex set which has $u$ and $v$ adjacent iff they are at distance $<= 2$ from each other, and then you're just looking at usual colorings of $G'$, right? $\endgroup$– Sam HopkinsCommented May 13, 2021 at 0:43
-
3$\begingroup$ Also known as an L(1,1) labelling…. $\endgroup$– Gordon RoyleCommented May 13, 2021 at 2:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
For a graph $G$, the $t$-th power of $G$ is the graph $G^t$ with the same vertex set as $G$ and where two vertices are adjacent in $G^t$ if they are connected by a path with at most $t$ edges in $G$. The distance-$t$ chromatic number of $G$, often denoted $\chi_t(G)$, is the chromatic number of $G^t$. As noted by Sam Hopkins in the comments, you are asking about $\chi_2(G)$. So, your colouring is known as a distance-$2$ colouring of $G$. See this paper of Kang and Pirot, where this terminology and notation is used.
answered May 13, 2021 at 0:56
-
1$\begingroup$ In addition, some people call it a 2-distance $k$-colouring, which seems odd to me. $\endgroup$ Commented May 13, 2021 at 2:59