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.


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.

  • $\begingroup$ Have there ever been distance-k colorings where distance-t vertices may be allowed to be the same colors? $\endgroup$ – Stone Oct 27 '17 at 15:30

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.