29 citations · 334 across the 88 of their papers we have counts for
9 papers · 1 filter
Induced subgraphs of graphs with large chromatic number. XII. Distant stars
Maria Chudnovsky, Alex Scott, Paul Seymour
The Gyarfas-Sumner conjecture asserts that if H is a tree then every graph with bounded clique number and very large chromatic number contains H as an induced subgraph. This is sti…
Induced subgraphs of graphs with large chromatic number. XI. Orientations
Maria Chudnovsky, Alex Scott, Paul Seymour
Fix an oriented graph H, and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomor…
Colouring perfect graphs with bounded clique number
Maria Chudnovsky, Aurélie Lagoutte, Paul Seymour +1
A graph is perfect if the chromatic number of every induced subgraph equals the size of its largest clique, and an algorithm of Grötschel, Lovász, and Schrijver from 1988 finds an…
Piercing axis-parallel boxes
Maria Chudnovsky, Sophie Spirkl, Shira Zerbib
Let $\F$ be a finite family of axis-parallel boxes in such that $\F$ contains no pairwise disjoint boxes. We prove that if $\F$ contains a subfamily $\M$ of pairwi…
Triangle-free graphs that do not contain an induced subdivision of are 3-colorable
Maria Chudnovsky, Chun-Hung Liu, Oliver Schaudt +3
We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vuskovic.
Perfect divisibility and 2-divisibility
Maria Chudnovsky, Vaidy Sivaraman
A graph is said to be -divisible if for all (nonempty) induced subgraphs of , can be partitioned into two sets such that and .…