{"id":"arxiv/2603.18754","url":"https://arxiv.org/abs/2603.18754","tags":["math.CO","cs.DM"],"score":0,"title":"The red-blue-yellow matching problem","domain":"math.CO","source":"arxiv","authors":["Manuel Aprile","Marco Di Summa"],"reviews":0,"subject":"math.CO","summary":"We consider the red-blue-yellow matching problem: given two natural numbers $k_R$, $k_B$ and a graph $G$ whose edges are colored red, blue or yellow, the goal is to find a matching of $G$ that contains exactly $k_R$ red edges and exactly $k_B$ blue edges, and is of maximum cardinality subject to these constraints. This is a natural generalization of the well known red-blue matching problem, whose complexity status is unknown: although a randomized polynomial-time algorithm exists, a deterministic algorithm has remained elusive for nearly four decades. The best known deterministic approach to…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-19","reactions":{}}