29 citations · 334 across the 88 of their papers we have counts for
6 papers · 2 filters
Fair representation by independent sets
Ron Aharoni, Noga Alon, Eli Berger +4
For a hypergraph let denote the minimal number of edges from covering . An edge of is said to represent {\em fairly} (resp. {\em almost fairly}) a part…
Large rainbow matchings in general graphs
Ron Aharoni, Eli Berger, Maria Chudnovsky +2
By a theorem of Drisko, any matchings of size in a bipartite graph have a partial rainbow matching of size . Inspired by discussion of Barát, Gyárfás and Sárközy, we…
Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
Maria Chudnovsky, Alex Scott, Paul Seymour
It is known that every graph of sufficiently large chromatic number and bounded clique number contains, as an induced subgraph, a subdivision of any fixed forest, and a subdivision…
The Erdös-Hajnal Conjecture---A Survey
Maria Chudnovsky
The Erdös-Hajnal conjecture states that for every graph , there exists a constant such that every graph with no induced subgraph isomorphic to has either a cl…
Approximately coloring graphs without long induced paths
Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl +2
It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on vertices, for fixed . We…
Disjoint paths in unions of tournaments
Maria Chudnovsky, Alex Scott, Paul Seymour
Given pairs of vertices of a digraph , how can we test whether there exist vertex-disjoint directed paths from to for ? T…