11 citations · 38 across the 16 of their papers we have counts for
23 papers
The chromatic number of -stable Kneser graphs
Carmen Arana, Penny Haxell, Tomáš Kaiser +1
Extending the notions of Kneser graphs and Schrijver graphs, we define the -stable Kneser graph (where and is a graph on vertices) as the grap…
Spanning subhypergraphs with degree constraints
Noga Alon, Penny Haxell, Aleksa Milojević +1
An old result of Tutte states that any -regular graph contains a spanning subgraph in which every vertex has degree or , for every . We generalize this s…
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…
Density of -critical signed graphs
Laurent Beaudou, Penny Haxell, Kathryn Nurse +2
We say that a signed graph is -critical if it is not -colorable but every one of its proper subgraphs is -colorable. Using the definition of colorability due to Naserasr,…
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 precise condition for independent transversals in bipartite covers
Stijn Cambie, Penny Haxell, Ross J. Kang +1
Given a bipartite graph in which any vertex in (resp.~) has degree at most (resp.~), suppose there is a partition of that is a refin…
Degree criteria and stability for independent transversals
Penny Haxell, Ronen Wdowinski
An \emph{independent transversal} (IT) in a graph with a given vertex partition is an independent set of vertices of (i.e. it induces no edges), that consists of one ve…
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…
Algorithms for weighted independent transversals and strong colouring
Alessandra Graf, David G. Harris, Penny Haxell
An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are k…
Finding Independent Transversals Efficiently
Alessandra Graf, Penny Haxell
We give an efficient algorithm that, given a graph and a partition of its vertex set, finds either an independent transversal (an independent set $\{v_1,\ldots…
Goldberg's Conjecture is true for random multigraphs
Penny Haxell, Michael Krivelevich, Gal Kronenberg
In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph , the chromatic index satisfies , where…
Ramsey-nice families of graphs
Ron Aharoni, Noga Alon, Michal Amir +5
For a finite family of fixed graphs let be the smallest integer for which every -coloring of the edges of the complete graph yields a…
A Stability Theorem for Matchings in Tripartite 3-Graphs
Penny Haxell, Lothar Narins
It follows from known results that every regular tripartite hypergraph of positive degree, with vertices in each class, has matching number at least . This bound is best p…
A note on intersecting hypergraphs with large cover number
Penny Haxell, Alex Scott
We give a construction of r-partite r-uniform intersecting hypergraphs with cover number at least r-4 for all but finitely many r. This answers a question of Abu-Khazneh, Barat, Po…
A Note on Schnyder's Theorem
Fidel Barrera-Cruz, Penny Haxell
We give an alternate proof of Schnyder's Theorem, that the incidence poset of a graph has dimension at most three if and only if is planar.
How to morph planar graph drawings
Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz +10
Given an -vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous tra…
Homological connectivity of random hypergraphs
Oliver Cooley, Penny Haxell, Mihyun Kang +1
We consider simplicial complexes that are generated from the binomial random 3-uniform hypergraph by taking the downward-closure. We determine when this simplicial complex is homol…
Morphing Schnyder drawings of planar triangulations
Fidel Barrera-Cruz, Penny Haxell, Anna Lubiw
We consider the problem of morphing between two planar drawings of the same triangulated graph, maintaining straight-line planarity. A paper in SODA 2013 gave a morph that consists…
Morphing Planar Graph Drawings with Unidirectional Moves
Fidel Barrera-Cruz, Penny Haxell, Anna Lubiw
Alamdari et al. showed that given two straight-line planar drawings of a graph, there is a morph between them that preserves planarity and consists of a polynomial number of steps…
On lower bounds for the matching number of subcubic graphs
Penny Haxell, Alex Scott
We give a complete description of the set of triples (a,b,c) of real numbers with the following property. There exists a constant K such that a n_3 + b n_2 + c n_1 - K is a lower b…
Extremal Hypergraphs for Ryser's Conjecture: Home-Base Hypergraphs
Penny Haxell, Lothar Narins, Tibor Szabó
Ryser's Conjecture states that any -partite -uniform hypergraph has a vertex cover of size at most times the size of the largest matching. For , the conjecture…
Extremal Hypergraphs for Ryser's Conjecture: Connectedness of Line Graphs of Bipartite Graphs
Penny Haxell, Lothar Narins, Tibor Szabó
In this paper we consider a natural extremal graph theoretic problem of topological sort, concerning the minimization of the (topological) connectedness of the independence complex…