19 citations · 43 across the 33 of their papers we have counts for
7 papers · 1 filter
The Structure of Metrizable Graphs
Maria Chudnovsky, Daniel Cizma, Nati Linial
A consistent path system in a graph is an intersection-closed collection of paths, with exactly one path between any two vertices in . We call metrizable if every consis…
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…
Graphs with no even holes and no sector wheels are the union of two chordal graphs
Tara Abrishami, Eli Berger, Maria Chudnovsky +1
Sivaraman conjectured that if is a graph with no induced even cycle then there exist sets satisfying such that the induced graph…
Reuniting -boundedness with polynomial -boundedness
Maria Chudnovsky, Linda Cook, James Davies +1
A class of graphs is -bounded if there is a function such that for all induced subgraphs of a graph in . If can be chose…
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…