34 citations · 188 across the 74 of their papers we have counts for
9 papers · 1 filter
A note on simplicial cliques
Maria Chudnovsky, Alex Scott, Paul Seymour +1
Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is…
Detecting a long even hole
Linda Cook, Paul Seymour
For each integer , we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least and even
Pure pairs. VI. Excluding an ordered tree
Alex Scott, Paul Seymour, Sophie Spirkl
A pure pair in a graph is a pair of disjoint sets of vertices such that either every vertex in is adjacent to every vertex in , or there are no edges bet…
Pure pairs. IV. Trees in bipartite graphs
Alex Scott, Paul Seymour, Sophie Spirkl
In this paper we investigate the bipartite analogue of the strong Erdos-Hajnal property. We prove that for every forest and every there exists , such that if has…
Holes with hats and Erdős-Hajnal
Maria Chudnovsky, Paul Seymour
A "hole-with-hat" in a graph is an induced subgraph of that consists of a cycle of length at least four, together with one further vertex that has exactly two neighbours in…
Finding an induced path that is not a shortest path
Eli Berger, Paul Seymour, Sophie Spirkl
We give a polynomial-time algorithm that, with input a graph and two vertices of , decides whether there is an induced -path that is longer than the shortest -…