Let $G$ be a simple graph. Consider the following edge coloring:

  1. We are allowed to use repetitive colors on some edges incident to a vertex such that the result does not contain a sequence of length $3$ of one color.

  2. The maximum different colors used for coloring the edges incident to a vertex is $s< \Delta(G)$.

Question 1: Is Question 2 a known graph theory problem?

Question 2: what is the smallest number of colors needed to color the edges of $G$ according to (1) and (2)?


Remark: Note that if $s=\Delta$ and without repetitive color then the problem reduces to usual edge coloring. this is useful for understanding this problem.

  • $\begingroup$ does a triangle count as a sequence of edges of length 3? $\endgroup$ – Fedor Petrov Oct 19 '17 at 17:25
  • 5
    $\begingroup$ Sounds like there's no such coloring on a path or cycle of length $3$ or more---since $\Delta(G)=2$, every vertex has to only use $s=1$ colors on its incident edges, so you end up just using one color. Might be an interesting question for other graphs though. $\endgroup$ – Zach Teitler Oct 19 '17 at 17:53
  • 1
    $\begingroup$ "Is this a known graph theory problem?" is hard to answer, since you have not actually stated a problem. $\endgroup$ – Gerry Myerson Oct 20 '17 at 0:51
  • 3
    $\begingroup$ @GerryMyerson Presumably Question 2 is the problem, and Question 1 is whether Question 2 is a known graph theory problem. I think the OP should edit to clarify. $\endgroup$ – Zach Teitler Oct 20 '17 at 3:17
  • 1
    $\begingroup$ I think that the condition $s<\Delta(G)$ is quite redundant, as one can add a star with many vertices (a $K_{1,N}$) to any graph. The edges of this star component can be colored with a single color. $\endgroup$ – domotorp Oct 20 '17 at 18:52

If I am interpreting your question correctly, I think this is essentially a star edge-coloring. The only difference is the added restriction $s<\Delta$ which slightly changes what is allowed at vertices of maximum degree.


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.