29 citations · 334 across the 88 of their papers we have counts for
6 papers · 2 filters
Disjoint dijoins
Maria Chudnovsky, Katherine Edwards, Ringi Kim +2
A dijoin in a digraph is a set of edges meeting every directed cut. D. R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then…
Disjoint paths in tournaments
Maria Chudnovsky, Paul Seymour, Alex Scott
Given pairs of vertices , , of a digraph , how can we test whether there exist vertex-disjoint directed paths from to for $1\le i\le…
Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures
Maria Chudnovsky, Paul Seymour, Alex Scott
Gyarfas conjectured in 1985 that for all , , every graph with no clique of size more than and no odd hole of length more than has chromatic number bounded by a functi…
Graphs with no induced five-vertex path or antipath
Maria Chudnovsky, Louis Esperet, Laetitia Lemoine +3
We prove that a graph contains no induced -vertex path and no induced complement of a -vertex path if and only if is obtained from -cycles and split graphs by repe…
Better 3-coloring algorithms: excluding a triangle and a seven vertex path
Flavia Bonomo-Braberman, Maria Chudnovsky, Jan Goedgebeur +4
We present an algorithm to color a graph with no triangle and no induced -vertex path (i.e., a -free graph), where every vertex is assigned a list of possible c…
Three-coloring graphs with no induced seven-vertex path I : the triangle-free case
Maria Chudnovsky, Peter Maceli, Mingxian Zhong
In this paper, we give a polynomial time algorithm which determines if a given triangle-free graph with no induced seven-vertex path is 3-colorable, and gives an explicit coloring…