As the title says I am interested in finding more information about the following graph coloring.
- Each vertex is colored with $k$ colors from a set of $C$ colors.
- The color sets of adjacent vertices must be disjoint
- The color sets of vertices at distance 2 can have at most 1 color in common
- The color sets of vertices at distance 3 can have at most 2 colors in common
- etc, so the color sets of vertices at distance d can have at most d-1 colors in common.
This means that the colors at vertex $v$ do not constrain the coloring of vertices at distance $> k$ and that the $k = 1$ case is just the 'standard' vertex coloring.
(As a very very very loose analogy we can think about the colors as electric charges with like colors repelling each other, but the repelling force becoming weaker as the distance decreases)
Because this directly generalizes the standard vertex coloring, I expect that some results about that coloring generalize to this context without too drastic modifications. In particular I am interested in if and in what form Brook's theorem, bounding the minimum needed number of colors $C$ in terms of $k$ and the maximal degree $\Delta$ of the graph generalizes.
Intuitively I would expect that for triangle free graphs with $\Delta \geq 3$ we get that we can color the graph with $C = k \Delta$ colors, but the very easy proof in the $k = 1$ case that Wikipedia gives does not immediately extend to the colorings above.
EDIT: this intuition was too optimistic: the complete bipartite graph $K_{3, 3}$ is a counterexample for $k > 1$. So let me tone it down to the following:
Intuitively I would expect that some version of Brook's theorem works for all $k$ in the sense that we can color the graph with $C = k \Delta$ colors, except for graphs in a finite number of explicitly described and easy to understand families of counterexamples (e.g. for $k = 1$ these are the odd cycles and complete graphs and no others, for higher $k$ there will be others, but my hope is they can still all be characterized in an easy way). However the very easy proof in the $k = 1$ case that Wikipedia gives does not immediately extend to the colorings above.
End of edit
I feel that the above definition is quite natural and I am not the first one to think about this. So any pointers to the literature would be welcome!
Best Answer
I think you are referring to t-tone coloring or t-tone chromatic number. Here are some references
https://faculty.math.illinois.edu/~west/regs/ttone.html
https://arxiv.org/abs/1108.4751
https://arxiv.org/abs/1210.0635