Algorithmic Aspect of Edge-Coloring

Vizing's Theorem states that a simple graph $G$ can be edge-colored with $Delta (G)+1$ colors, where $Delta (G)$ is the degree of the graph $G$. This immediately introduces the classification problem -- if chromatic index $chi '(G)=Delta (G)$, then $G$ is in class one; otherwise $G$ is in class two. We extend the proof of Vizing's Theorem to introduce a new idea that if we want to color an edge of $G$ and this edge satisfies an unsaturated condition under $k$ colors, for some $k leq Delta (G)$, then this edge can be colored with one of $k$ colors. Thus, for any coloring order, each edge of a simple graph $G$ satisfies the unsaturated condition under $Delta (G)+1$ colors. If we find a feasible edge-coloring order of $G$ such that each edge can satisfy the unsaturated condition under $Delta (G)$ colors, then $G$ is in class one. We show that if the subgraph induced by all $Delta (G)$-vertices is a forest or a cactus in which each end block is an edge, then $G$ has such a feasible coloring order and $G$ is in class one. We also find such a feasible coloring order for reduced proper interval graphs.