12 citations · 26 across the 7 of their papers we have counts for
6 papers · 1 filter
Induced subgraphs and tree decompositions V. One neighbor in a hole
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +3
What are the unavoidable induced subgraphs of graphs with large treewidth? It is well-known that the answer must include a complete graph, a complete bipartite graph, all subdivisi…
Polynomial bounds for chromatic number VII. Disjoint holes
Maria Chudnovsky, Alex Scott, Paul Seymour +1
A hole in a graph is an induced cycle of length at least four, and a -multihole in is a set of pairwise disjoint and nonadjacent holes. It is well known that if does…
Strengthening Rodl's theorem
Maria Chudnovsky, Alex Scott, Paul Seymour +1
What can be said about the structure of graphs that do not contain an induced copy of some graph H? Rodl showed in the 1980s that every H-free graph has large parts that are very d…
Concatenating bipartite graphs
Maria Chudnovsky, Patrick Hompe, Alex Scott +2
Let and let be disjoint nonempty subsets of a graph , where every vertex in has at least neighbours in , and every vertex in has at least…
Four-coloring -free graphs. II. Finding an excellent precoloring
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
This is the second paper in a series of two. The goal of the series is to give a polynomial time algorithm for the -coloring problem and the -precoloring extension problem re…
Four-coloring -free graphs. I. Extending an excellent precoloring
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
This is the first paper in a series whose goal is to give a polynomial time algorithm for the -coloring problem and the -precoloring extension problem restricted to the class…