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