This question is related to my previous post: New edge coloring problem in graph theory.

Added: 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$.

Obviously $s\leq \Delta$. Is the following clime true? Could someone provide a counterexample or a sketch of proof for this clime?

Clime (Edited after Chris Godsil Answer): Edges of every simple graph can be colored due to above coloring with at most $s+1$ color. where $s=\lfloor\frac{\Delta+1}{2}\rfloor$+1.


1 Answer 1


It might be less confusing if you just claimed/asked if $\lfloor \frac{\Delta+3}2\rfloor$ colors suffice. However it is not correct. The $10$ edges of the complete graph $K_5$ can not be $3$ colored without creating a monochromatic $3$ edge path (which might be closed, i.e. a triangle.)

Here is a sketch which seems a little long but does the job:

  1. Note that $K_4$ can , as claimed, be colored with $3$ colors. However $2$ colors are not enough.

  2. In a possible $3$ edge coloring of $K_5$ observe that no vertex can touch $3$ (or $4$) edges of the same color because then the edges of the remaining vertices are restricted to the other two colors, and that contradicts 1.

  3. There are at least $4$ edges with the same color, say $a.$ Suppose $12,13$ are colored $a$. Then neither of $14,15$ is. Also none of $23,24,25,34,35$ can have color $a.$ But that leaves only $45$ which (so far) could have color $a$ and that is only three edges, not four.


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.