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$ Commented Oct 19, 2017 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$ Commented Oct 19, 2017 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$ Commented Oct 20, 2017 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$ Commented Oct 20, 2017 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
    Commented Oct 20, 2017 at 18:52

1 Answer 1


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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.