Edge-coloring almost bipartite multigraphs

• Edge-coloring and list-edge-coloring are well understood for bipartite graphs.
• We study these two problems for almost bipartite graphs obtained by inserting vertices in edges.
• We show that the number of colors for degree d   never exceeds d+1d+1 and is often just d.

Bipartite multigraphs have chromatic index equal to the largest degree d. We consider multigraphs obtained by inserting k   vertices in edges of a connected bipartite multigraph, and show that the chromatic index may increase to at most d+1d+1. We further show that (1) the chromatic index always increases if k=1k=1 when the original bipartite multigraph is regular, but does not increase for k=1k=1 if the bipartite multigraph is not regular; (2) the chromatic index does not increase if k=2k=2 (regular or not); (3) the chromatic index may increase if k=3k=3 when the original bipartite multigraph is regular, but does not increase for k=3k=3 if the bipartite multigraph is not regular; (4) the chromatic index does not increase if k=4k=4 (regular or not); (5) the chromatic index increases for infinitely many 3-regular bipartite graphs and each k⩾3k⩾3 odd, and (6) the chromatic index does not increase for infinitely many 3-regular bipartite graphs and each k⩾3k⩾3 (even or odd).We finally study the list chromatic index of such multigraphs and show that it does not increase past d+1d+1 either, in fact in some sense it stays almost d. All the results presented here render polynomial-time algorithms, since the proofs are based on bipartite graph matching and stable marriage.