4 papers
On the chromatic number of the union of comparability graphs
Wouter Cames van Batenburg, Maria Chudnovsky, 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 clique…
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átal…
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 …
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 chose…