Better Approximation for Edge 2-Coloring on Bipartite Graphs

18.9.2026

  | IMDEA Software Institute

Tuesday, September 22, 2026.



11:00am Meeting room 302 & Zoom3 https://zoom.us/j/3911012202 (pass: @s3)
Alex Popa, Full Professor, University of Bucharest

Better Approximation for Edge 2-Coloring on Bipartite Graphs
Abstract:

An edge 2-coloring is a coloring of the edges of an undirected graph such that each vertex is incident to edges of at most two distinct colors. In the maximum edge 2-coloring problem, the input is an undirected graph, and the goal is to find an edge 2-coloring using the maximum possible number of colors.

The maximum edge 2-coloring problem is known to be APX-hard, and the best known approximation factor is 2. Approximation algorithms with a factor better than 2 are known only for particular classes of graphs that have a perfect matching.

In this talk, we present a 9/5-approximation algorithm for the maximum edge 2-coloring problem on bipartite graphs.



https://software.imdea.org/events/invited-talks/2026/09-22