Consecutive colorings of the edges of general graphs (Q5959097)

A consecutive (or interval) edge-coloring of a graph \(G = (V, E)\) is a map \(f : E \rightarrow \mathbb{N}\) such that the colors of edges at each vertex are distinct and form an interval of integers. It follows from the well-known NP-completenes result for edge-colorings that deciding whether a graph is consecutive edge-colorable is NP-complete. The authors then prove that for consecutive edge-colorable (triangle-free) graphs with \(n \geq 3\) vertices, the maximum number of colors used in a consecutive edge-coloring is at most \(2n - 4\) (\(n - 1\), respectively). They further determine the minimum number of pendant edges to be attached to a cycle (a wheel, a complete graph) such that the resulting graph admits a consecutive edge-coloring.