4 papers
Constructing graphs with no independent transversals
Penny Haxell, Ronen Wdowinski
Given a graph and a partition of its vertex set, an independent transversal (IT) is an independent set of that contains one vertex from each block in . Various suffi…
A Counterexample to a Conjecture of Lovász
Alexander Clow, Penny Haxell, Bojan Mohar
In 1975 Lovász conjectured that every -partite, -uniform hypergraph contains vertices whose deletion reduces the matching number. If true, this statement would imply a…
A bounded diameter strengthening of KÅnig's Theorem
Louis DeBiasio, António Girão, Penny Haxell +1
K\H onig's theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at mos…
Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole
Penny Haxell, Tibor Szabó
In the max-min allocation problem a set of players are to be allocated disjoint subsets of a set of indivisible resources, such that the minimum utility among all players i…