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…
Geometric graphs with exponential chromatic number and arbitrary girth
Matija Bucić, James Davies
In 1975 Erdős initiated the study of the following very natural question. What can be said about the chromatic number of unit distance graphs in that have large girt…
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…