3
$\begingroup$

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!

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Yes this sounds exactly like the thing I was looking for! $\endgroup$
    – Vincent
    Dec 27, 2021 at 15:45
  • 1
    $\begingroup$ Wait, are you the first author of the article linked third? $\endgroup$
    – Vincent
    Dec 27, 2021 at 16:33
  • 1
    $\begingroup$ haha...yes. that's how I recognized the topic. but I haven't thought about it for a long time, so I didn't want to think about any of the specific math you wrote...sorry! $\endgroup$
    – dbal
    Dec 27, 2021 at 18:50
  • $\begingroup$ No problem, I'll just read the references! $\endgroup$
    – Vincent
    Dec 27, 2021 at 19:45

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.