On the $1.1$ Edge-Coloring of Multigraphs
Takao Nishizeki, Kenichi Kashiwagi · SIAM Journal on Discrete Mathematics · 1990
A new upper bound is proved for the chromatic index $q^* ( G )$ of multigraphs $G = ( V,E )$. Let $d ( G )$ be the maximum degree of G, and let \[ p ( G ) = \text{MAX} \{ \lceil 2 | E(X) |/ ( | X | - 1) \rceil :X \subset V, | X | e 1\,\text{and odd} \} \] where $E( X )$ is the set of edges in the subgraph of G induced by X. The upper bound is expressed in terms of the two trivial lower bounds $d ( G )$ and $p ( G )$ as follows: \[ q^* ( G )\leqq \text{MAX} \{ p ( G ), \lfloor 1.1 d ( G ) + 0.8 \rfloor \}. \] The proof yields an algorithm which edge-colors any given multigraph G with at most $\lfloor 1.1q^* ( G ) + 0.8 \rfloor $ colors. The running time is $O ( | E | ( d ( G ) + | V | ) )$ and the storage space is $O ( | E | )$.