5 citations · 12 across the 9 of their papers we have counts for
7 papers · 1 filter
Vu's conjecture holds for claw-free graphs
Linda Cook, Ross J. Kang, Eileen Robinson +1
Given a graph , let denote the maximum number of neighbors any two distinct vertices of have in common. Vu (2002) proposed that, provided is not too small…
Excluding the fork and antifork
Maria Chudnovsky, Linda Cook, Paul Seymour
The fork is the tree obtained from the claw by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs t…
On recognition algorithms and structure of graphs with restricted induced cycles
Linda Cook
This is my PhD thesis which was defended in May 2021. We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of…
On tree decompositions whose trees are minors
Pablo Blanco, Linda Cook, Meike Hatzel +3
In 2019, Dvořák asked whether every connected graph has a tree decomposition so that is a subgraph of and the width of is bounded…
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of
Linda Cook, Tomáš Masařík, Marcin Pilipczuk +2
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph is -free if does not contain as an induced sub(di)graph. The…
Graphs with all holes the same length
Linda Cook, Jake Horsfield, Myriam Preissmann +5
A graph is "-holed" if all its induced cycles of length at least four have length exactly . We give a complete description of the -holed graphs for each $\ell\ge…
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