# New edge coloring problem in graph theory

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)?

Update.

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.

• does a triangle count as a sequence of edges of length 3? Oct 19, 2017 at 17:25
• 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. Oct 19, 2017 at 17:53
• "Is this a known graph theory problem?" is hard to answer, since you have not actually stated a problem. Oct 20, 2017 at 0:51
• @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. Oct 20, 2017 at 3:17
• 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. Oct 20, 2017 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.