research
∙
09/05/2023
Boxicity and Interval-Orders: Petersen and the Complements of Line Graphs
The boxicity of a graph is the smallest dimension d allowing a represent...
share
research
∙
11/23/2022
Shortest Odd Paths in Conservative Graphs: Connections and Complexity
We present some reductions between optimization problems for undirected ...
research
∙
06/05/2022
Packing, Hitting, and Coloring Squares
Given a family of squares in the plane, their packing problem asks for t...
research
∙
02/25/2020
Integer Plane Multiflow Maximisation:Flow-Cut Gap and One-Quarter-Approximation
In this paper, we bound the integrality gap and the approximation ratio ...
research
∙
12/11/2019
Ear-Slicing for Matchings in Hypergraphs
We study when a given edge of a factor-critical graph is contained in a ...
research
∙
10/24/2019
Color-critical Graphs and Hereditary Hypergraphs
A quick proof of Gallai's celebrated theorem on color-critical graphs is...
research
∙
11/18/2018