12 citations · 147 across the 77 of their papers we have counts for
12 papers · 2 filters
Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole
Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
A clock is a graph consisting of an induced cycle and a vertex not in with at least two non-adjacent neighbours in . We show that every clock-free graph of large treewid…
List--Coloring -free graphs for all
Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
Given an integer and a graph , we prove that, assuming PNP, the List--Coloring Problem restricted to -free graphs can be solved in polynomial time if and only…
Induced subgraphs and tree decompositions XIII. Basic obstructions in -free graphs for finite
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
Unlike minors, the induced subgraph obstructions to bounded treewidth come in a large variety, including, for every , the -basic obstructions: the graphs and…
Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
Given an integer , we say a graph is -pinched if does not contain an induced subgraph consisting of cycles, all going through a single common vertex…
Induced subgraphs and tree decompositions XI. Local structure in even-hole-free graphs of large treewidth
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
We prove a conjecture of Sintiari and Trotignon that every even-hole-free graph of sufficiently large treewidth contains a four-vertex induced subgraph with at least five edges (th…
Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2
A generalized -pyramid is a graph obtained from a certain kind of tree (a subdivided star or a subdivided cubic caterpillar) and the line graph of a subdivided cubic caterpillar…
On heroes in digraphs with forbidden induced forests
Alvaro Carbonero, Hidde Koerts, Benjamin Moore +1
We continue a line of research which studies which hereditary families of digraphs have bounded dichromatic number. For a class of digraphs , a hero in i…
Tree independence number I. (Even hole, diamond, pyramid)-free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +3
The tree-independence number tree-, first defined and studied by Dallard, Milanič and Štorgel, is a variant of treewidth tailored to solving the maximum independent set problem.…
Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
The celebrated Erdős-Pósa Theorem, in one formulation, asserts that for every , graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of cy…
Hitting all maximum stable sets in -free graphs
Sepehr Hajebi, Yanjia Li, Sophie Spirkl
We prove that every -free graph of bounded clique number contains a small hitting set of all its maximum stable sets. More generally, let us say a class of graph…
Induced subgraphs and tree decompositions VIII. Excluding a forest in (theta, prism)-free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2
Given a graph , we prove that every (theta, prism)-free graph of sufficiently large treewidth contains either a large clique or an induced subgraph isomorphic to , if and onl…
The Kromatic Symmetric Function: A -theoretic Analogue of
Logan Crew, Oliver Pechenik, Sophie Spirkl
Schur functions are a basis of the symmetric function ring that represent Schubert cohomology classes for Grassmannians. Replacing the cohomology ring with -theory yields a rich…