4 papers
Jump-systems of -paths
Mouna Sadli, András Sebő
Jump systems are sets of integer vectors satisfying a simple axiom, generalizing matroids, also delta-matroids, and well-kown combinatorial examples such as degree sequences of sub…
Integer Plane Multiflow Maximisation : Flow-Cut Gap and One-Quarter-Approximation
Naveen Garg, Nikhil Kumar, András Sebő
In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the un…
Ear-Slicing for Matchings in Hypergraphs
András Sebő
We study when a given edge of a factor-critical graph is contained in a matching avoiding exactly one, pregiven vertex of the graph. We then apply the results to always partition t…
Color-critical Graphs and Hereditary Hypergraphs
András Sebő
A quick proof of Gallai's celebrated theorem on color-critical graphs is given from Gallai's simple, ingenious lemma on factor-critical graphs, in terms of partitioning the vertex-…