Linda Cook gave a talk on the local certification protocol for monadic second-order property on graphs of bounded tree-width at the Discrete Math Seminar

Linda Cook

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 (MSO2), a powerful framework that can express properties such as non-k-colorability, Hamiltonicity, and H-minor-freeness. Unfortunately, in general, there are MSO2-expressible properties that cannot be certified without huge certificates. For instance, non-3-colorability requires certificates of size Ω(n2/logn) on general n-vertex graphs (Göös, Suomela 2016). Hence, we impose additional structural restrictions on the graph. Inspired by their importance in centralized computing and Robertson-Seymour Graph Minor theory, we consider graphs of bounded treewidth. We provide a local certification protocol for certifying any MSO2-expressible property on graphs of bounded treewidth and, consequently, a local certification protocol for certifying bounded treewidth. That is, for each integer k and each MSO2-expressible property Π, we give a local certification protocol to certify that a graph satisfies Π and has treewidth at most k using certificates of size O(logn) (which is asymptotically optimal). Our result improves upon the works of Fraigniaud, Montealegre, Rapaport, and Todinca (Algorithmica 2024),  Bousquet, Feuilloley, Pierron (PODC 2022), and the very recent work of Baterisna and Chang (PODC 2025).

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 H, there is a polynomial p such that for every positive integer s, every graph of average degree at least p(s) contains either Ks,s as a subgraph or contains an induced subdivision of H. This improves upon a result of Kühn and Osthus from 2004 who proved it for graphs whose average degree is at least triply exponential in s and a recent result of Du, Girão, Hunter, McCarty and Scott for graphs with average degree at least singly exponential in s.

As an application, we prove that the class of graphs that do not contain an induced subdivision of Ks,t is polynomially χ-bounded. In the case of K2,3, this is the class of theta-free graphs, and answers a question of Davies. Along the way, we also answer a recent question of McCarty, by showing that if G is a hereditary class of graphs for which there is a polynomial p such that every bipartite Ks,s-free graph in G has average degree at most p(s), then more generally, there is a polynomial p such that every Ks,s-free graph in G has average degree at most p(s). Our main new tool is an induced variant of the Kővári-Sós-Turán theorem, which we find to be of independent interest.

This is joint work with Romain Bourneuf (ENS de Lyon), Matija Bucić (Princeton), and James Davies (Cambridge),

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:05Obstructions for dense analogs of tree-depthSang-il OUM
10:05-10:20Structural and extremal results for twin-widthKevin HENDREY
10:20-10:35Down-sets in combinatorial posetsRutger CAMPBELL
10:35-10:50Reuniting 𝜒-boundedness with polynomial 𝜒-boundednessLinda COOK

Linda Cook, Orientations of P4 bind the dichromatic number

An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph D is H-free if D does not contain H as an induced sub(di)graph.

The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest F, there is some function f such that every F-free graph G with clique number ω(G) has chromatic number at most f(ω(G)).

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 D is the minimum number of colors required to color the vertex set of D so that no directed cycle in D is monochromatic. Aboulker, Charbit, and Naserasr’s χ-boundedness conjecture states that for every oriented forest F, there is some function f such that every F-free oriented graph D has dichromatic number at most f(ω(D)), where ω(D) is the size of a maximum clique in the graph underlying D.

In this talk, we perform the first step towards proving Aboulker, Charbit, and Naserasr’s χ-boundedness conjecture by showing that it holds when F is any orientation of a path on four vertices.

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 for every 7 (joint work with Jake Horsfield, Myriam Preissmann, Paul Seymour, Ni Luh Dewi Sintiari, Cléophée Robin, Nicolas Trotignon, and Kristina Vuškovíc.

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 vV(G). In 2002, Conforti, Cornuéjols, Kapoor, and Vuškovíc gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2003, Chudnovsky, Kawarabayashi, and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019, Chudnovsky, Scott, Seymour, and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year, Chudnovsky, Scott, and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least for any fixed integer 5. I will present a polynomial-time algorithm (joint work with Paul Seymour) to test whether a graph contains an even hole of length at least for any fixed integer 4.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.