34 citations · 188 across the 74 of their papers we have counts for
4 papers · 1 filter
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…
Majority Colourings of Digraphs
Stephan Kreutzer, Sang-il Oum, Paul Seymour +2
We prove that every digraph has a vertex 4-colouring such that for each vertex , at most half the out-neighbours of receive the same colour as . We then obtain several re…
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…