4
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ does a triangle count as a sequence of edges of length 3? $\endgroup$
    – Fedor Petrov
    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$
    – Zach Teitler
    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$
    – Gerry Myerson
    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$
    – Zach Teitler
    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

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .