12 citations · 26 across the 7 of their papers we have counts for
7 papers
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…
-colouring -free graphs in subexponential time
Carla Groenland, Karolina Okrasa, Pawel Rzążewski +3
A graph is called -free if it does not contain the path on vertices as an induced subgraph. Let be a multigraph with the property that any two distinct vertices share…
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…