Skip to main content
added 2 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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$ colouringdistance-$2$ colouring of $G$. See this paper of Kang and Pirot, where this terminology and notation is used.

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.

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.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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.