3 citations · 8 across the 15 of their papers we have counts for
18 papers
Basis Number and Pathwidth
Babak Miraftab, Pat Morin, Yelena Yuditsky
We prove two results relating the basis number of a graph to path decompositions of . Our first result shows that the basis number of a graph is at most four times its pathw…
The asymptotic -boundedness of hereditary families
Bruce Reed, Yelena Yuditsky
A family of graphs is asymptotically -bounded with bounding function if almost every graph in the family satisfies . A graph is -free if…
Typical -free graphs
Bruce Reed, Yelena Yuditsky
We prove that for every tree which is not an edge, for almost every graph which does not contain as an induced subgraph, has a partition into parts cert…
Face covers and rooted minors in bounded genus graphs
Samuel Fiorini, Stefan Kober, Michał T. Seweryn +2
A {\em rooted graph} is a graph together with a designated vertex subset, called the {\em roots}. In this paper, we consider rooted graphs embedded in a fixed surface. A collection…
On graph classes with constant domination-packing ratio
Marthe Bonamy, Mónika Csikós, Anna Gujgiczer +1
The dominating number of a graph is the minimum size of a vertex set whose closed neighborhood covers all the vertices of the graph. The packing number of is…
Integer programs with nearly totally unimodular matrices: the cographic case
Manuel Aprile, Samuel Fiorini, Gwenaël Joret +4
It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix whose subdeterminants are all bounded by a constant in absolute value, ca…
Total Matching and Subdeterminants
Luca Ferrarini, Samuel Fiorini, Stefan Kober +1
In the total matching problem, one is given a graph with weights on the vertices and edges. The goal is to find a maximum weight set of vertices and edges that is the non-incid…
On Separating Path and Tree Systems in Graphs
Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel +6
We explore the concept of separating systems of vertex sets of graphs. A separating system of a set is a collection of subsets of such that for any pair of distinct element…
Conflict-Free Colouring of Subsets
Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky +1
We introduce and study conflict-free colourings of -subsets in hypergraphs. In such colourings, one assigns colours to all subsets of vertices of cardinality such that in an…
Integer programs with bounded subdeterminants and two nonzeros per row
Samuel Fiorini, Gwenaël Joret, Stefan Weltge +1
We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at…
Weak Coloring Numbers of Intersection Graphs
Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt +1
Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for each natural number , we seek a vertex ordering such every vertex can (weakly respec…
On Multicolour Ramsey Numbers and Subset-Colouring of Hypergraphs
Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky +1
For and , write if every hyperedge colouring with colours of the complete -uniform hypergraph on vertices has a mon…
Typical structure of hereditary graph families. II. Exotic examples
Sergey Norin, Yelena Yuditsky
A graph is -free if it does not contain an induced subgraph isomorphic to . The study of the typical structure of -free graphs was initiated by Erdős, Kleitman and Rot…
Typical structure of hereditary graph families. I. Apex-free families
Sergey Norin, Yelena Yuditsky
A family of graphs is hereditary if is closed under isomorphism and taking induced subgraphs. The speed of is the sequence $\{|\mathcal{F}…
The --Net Problem
Noga Alon, Bruno Jartoux, Chaya Keller +2
We study a natural generalization of the classical -net problem (Haussler--Welzl 1987), which we call the "--net problem": Given a hypergraph on vertices and parameter…
Almost all string graphs are intersection graphs of plane convex sets
János Pach, Bruce Reed, Yelena Yuditsky
A {\em string graph} is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all s…
Erdős-Szekeres without induction
Sergey Norin, Yelena Yuditsky
Let be the minimal integer such that any set of points in the plane in general position contains points in convex position. The problem of estimating wa…
Polychromatic Coloring for Half-Planes
Shakhar Smorodinsky, Yelena Yuditsky
We prove that for every integer , every finite set of points in the plane can be -colored so that every half-plane that contains at least points, also contains at leas…