On July 22, 2025, Linda Cook from the University of Amsterdam gave a talk at the Discrete Math Seminar on the local certification protocol for monadic second-order property on graphs of bounded tree-width. The title of her talk was “A tight algorithmic meta-theorem for distributed certification within bounded treewidth graphs“.
Linda Cook, A tight algorithmic meta-theorem for distributed certification within bounded treewidth graphs
A local certification of a graph property is a protocol in which nodes are given “certificates of a graph property” that allow the nodes to check whether their network has this property while only communicating with their local network. The key property of a local certification is that if certificates are corrupted, some node in the network will be able to recognize this. Inspired by practical concerns, the aim in LOCAL certification is to minimize the maximum size of a certificate.
In this talk we introduce local certification and open problems in the area and present some recent joint work with Eunjung Kim and Tomáš Masařík, A Tight Meta-theorem for LOCAL Certification of MSO2 Properties within Bounded Treewidth Graphs.
In this work, instead of considering a specific graph property and developing a local certification protocol tailor-made for this property, we aim for generic protocols that can certify any property expressible in a certain logical framework. We consider Monadic Second Order Logic (MSO
Linda Cook gave a talk on bounding the average degree of a graph with no subgraph isomorphic to a fixed complete bipartite subgraph or a subdivision of a fixed graph at the Discrete Math Seminar
On March 12, 2024, Linda Cook from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar about bounding the average degree of a graph with no subgraph isomorphic to a fixed complete bipartite graph or a subdivision of a fixed graph by a polynomial function of the size of the complete bipartite graph. The title of her talk was “On polynomial degree-boundedness“.
Linda Cook, On polynomial degree-boundedness
We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak, that for every graph
As an application, we prove that the class of graphs that do not contain an induced subdivision of
This is joint work with Romain Bourneuf (ENS de Lyon), Matija Bucić (Princeton), and James Davies (Cambridge),
Linda Cook was interviewed on a video posted by the Ministry of Science and ICT
Linda Cook of the IBS Discrete Mathematics Group was interviewed on a video posted by the Ministry of Science and ICT, featuring international researchers in Korea.
Linda Cook gave a talk on bounding the dichromatic number after forbidding a fixed orientation of a path at the Discrete Math Seminar
On August 22, 2023, Linda Cook from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on bounding the dichromatic number of a directed graph not having an induced subgraph isomorphic to a fixed orientation of a path. The title of her talk was “Orientations of P_4 bind the dichromatic number“.
Open Symposium at the Discrete Mathematics Group
On July 13, 2023, the Open Symposium at the Discrete Mathematics Group was held. There were four talks by the members of the Discrete Mathematics Group.
9:40-10:05 | Obstructions for dense analogs of tree-depth | Sang-il OUM |
10:05-10:20 | Structural and extremal results for twin-width | Kevin HENDREY |
10:20-10:35 | Down-sets in combinatorial posets | Rutger CAMPBELL |
10:35-10:50 | Reuniting 𝜒-boundedness with polynomial 𝜒-boundedness | Linda COOK |
Linda Cook, Orientations of bind the dichromatic number
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph
The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest
Aboulker, Charbit, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph
In this talk, we perform the first step towards proving Aboulker, Charbit, and Naserasr’s
Linda Cook gave a talk on (1) the recognition algorithm for graphs with no long even holes and (2) the structure of graphs with no holes of length≠𝓁 at the Discrete Math Seminar
On August 17, 2021, Linda Cook from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on (1) a polynomial-time algorithm to detect long even holes and (2) a structure of graphs with no holes of length≠𝓁 for a fixed 𝓁≥7. The title of her talk was “Two results on graphs with holes of restricted lengths“.
Linda Cook, Two results on graphs with holes of restricted lengths
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 certain types in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002, Conforti, Cornuéjols, Kapoor, and Vuškovíc provided a structural description of the class of even-hole-free graphs. I will describe the structure of all graphs that contain only holes of length
Analysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities. In 1991, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex