3 papers
math.CO2026
Matchings: Source, Goal and Faithful Companion
András Sebő
Matchings were among the earliest motivations for graph theory. They subsequently remained a central goal, inspiring the development of new mathematical tools that went well beyond…
math.CO2018
How many matchings cover the nodes of a graph?
Dehia Ait Ferhat, Zoltán Király, András Sebő +1
Given an undirected graph, are there matchings whose union covers all of its nodes, that is, a matching--cover? A first, easy polynomial solution from matroid union is possi…
cs.DM2017
The Salesman's Improved Tours for Fundamental Classes
Sylvia Boyd, András Sebö
Finding the exact integrality gap for the LP relaxation of the metric Travelling Salesman Problem (TSP) has been an open problem for over thirty years, with little progress mad…