5 papers
Facial diagrams and cycle double cover
Babak Ghanbari, Robert Šámal
We approach the cycle double cover conjecture by looking for a circular 2-cell embedding of cubic graphs on an arbitrary surface. It is easy to see that if such an embedding exists…
A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
Babak Ghanbari, Robert Šámal
We present a near-linear-time algorithm that, given a bridgeless cubic graph, finds a perfect matching intersecting every 3-edge-cut in exactly one edge. This improves over a cubic…
Bolzano: Case Studies in LLM-Assisted Mathematical Research
Martin Balko, Jan Grebík, Pavel Hubáček +5
We report new results on eight problems in mathematics and theoretical computer science, produced with the assistance of Bolzano, an open-source multi-agent LLM system. Bolzano orc…
Approximate cycle double cover
Babak Ghanbari, Robert Šámal
The Cycle double cover (CDC) conjecture states that for every bridgeless graph , there exists a family of cycles such that each edge of the graph is contained in e…
On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
Babak Ghanbari, Robert Šámal
We present an algorithm for finding a perfect matching in a -edge-connected cubic graph that intersects every -edge cut in exactly one edge. Specifically, we propose an algor…