Publications (15)
On polynomial degree-boundedness
Romain Bourneuf, Matija BuciÄ, Linda Cook +1
We prove a conjecture of Bonamy, Bousquet, Pilipczuk, RzÄ Å¼ewski, Thomassé, and Walczak, that for every graph , there is a polynomial such that for every positive integer…
Reconstructing Graphs from Connected Triples
Paul Bastide, Linda Cook, Jeff Erickson +4
We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In…
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 bounde…
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 ch…
A tight local algorithm for the minimum dominating set problem in outerplanar graphs
Marthe Bonamy, Linda Cook, Carla Groenland +1
We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We…
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 the chromatic number of the union of comparability graphs
Maria Chudnovsky, Wouter Cames van Batenburg, Linda Cook +3
Resolving in a strong sense a problem of Gyárfás on the union of two perfect graphs, we prove that for every pair of positive integers and , there is a graph with cliq…
A Tight Meta-theorem for LOCAL Certification of MSO Properties within Bounded Treewidth Graphs
Linda Cook, Eun Jung Kim, Tomáš MasaÅÃk
Distributed networks are prone to errors so verifying their output is critical. Hence, we develop LOCAL certification protocols for graph properties in which nodes are given certif…
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
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…
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 smal…
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…
Colouring t-perfect graphs
Maria Chudnovsky, Linda Cook, James Davies +2
Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities (including edge inequalities). In 1975, Chváta…
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…
Local certification of forbidden subgraphs
Nicolas Bousquet, Linda Cook, Laurent Feuilloley +2
Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph de…