12 citations · 147 across the 77 of their papers we have counts for
11 papers · 2 filters
Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth
Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
The pathwidth of a graph is the smallest such that can be constructed from a sequence of graphs, each on at most vertices, by gluing them together i…
Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth
Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
Two sets of vertices in a graph are "anticomplete" if and there is no edge in with an end in and an end in . We prove that every graph $…
Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors
Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
We prove that for every graph with a sufficiently large complete bipartite induced minor, either has an induced minor isomorphic to a large wall, or contains a large co…
Maximum -colourable induced subgraphs in -free graphs
Cicely Henderson, Evelyne Smith-Roberge, Sophie Spirkl +1
We show that for any nonnegative integer , the Weighted Maximum List--Colourable Induced Subgraph problem can be solved in polynomial time for input graphs that do not contai…
Orientations of graphs with at most one directed path between every pair of vertices
Barbora Dohnalová, Jiří Kalvoda, Gaurav Kucheriya +1
Given a graph , we say that an orientation of is a KT orientation if, for all , there is at most one directed path (in any direction) between and .…
Tree Independence Number IV. Even-hole-free Graphs
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2
We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constan…
Tree independence number II. Three-path-configurations
Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov +1
A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is…
The sandwich problem for odd-hole-free and even-hole-free graphs
Kathie Cameron, Aristotelis Chaniotis, Celina M. H. de Figueiredo +1
For a property of graphs, the -\textsc{Sandwich-Problem}, introduced by Golumbic and Shamir (1993), is the following: Given a pair of graphs …
Graphs of bounded chordality
Aristotelis Chaniotis, Babak Miraftab, Sophie Spirkl
A hole in a graph is an induced subgraph which is a cycle of length at least four. A graph is chordal if it contains no holes. Following McKee and Scheinerman (1993), we define the…
Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2
We prove that for every integer there exists an integer such that every -vertex even-hole-free graph with no clique of size has treewidth at most $c_t\…
On prime Cayley graphs
Maria Chudnovsky, Michal Cizek, Logan Crew +4
The decomposition of complex networks into smaller, interconnected components is a central challenge in network theory with a wide range of potential applications. In this paper, w…