1
$\begingroup$

I'm wondering whether or not there is a symbol or value such as the chromatic number of a graph that asks

What is the minimum coloring of the graph such that not only adjacent vertices have different colors, but vertices adjacent to a mutual vertices have different colors.

I'm just curious on whether this is a thing, or is it question that is easily related to the chromatic number and thus is not really thought much about.

$\endgroup$

1 Answer 1

1
$\begingroup$

I've seen this called the distance-2 coloring, where distance-k coloring asks for a vertex coloring where every two vertices of the same color are more than k steps apart. It's used in algorithms and computational results, but I'm not familiar with many of its properties.

$\endgroup$
3
  • $\begingroup$ Have there ever been distance-k colorings where distance-t vertices may be allowed to be the same colors? $\endgroup$
    – Stone
    Oct 27, 2017 at 15:30
  • $\begingroup$ When you search literature for distance-$k$ coloring, make sure you check out coloring of graph powers. A distance-$k$ coloring of graph $G$ is basically a coloring of the power graph $G^k$. In particular, for distance-2 coloring, also check coloring of square of graphs. $\endgroup$ Jan 27, 2020 at 6:29
  • $\begingroup$ Also distance-2 coloring has a wide number of applications. $\endgroup$ Jan 27, 2020 at 6:30

You must log in to answer this question.

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