2 citations · 3 across the 14 of their papers we have counts for
22 papers · 1 filter
Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound
Wouter Cames van Batenburg, Jan Goedgebeur, Jorik Jooken
In 1979, Albertson and Berman conjectured that every planar graph contains an induced forest of order at least . This long-standing conjecture was recently disproved…
Asymptotically attaining the Moore bound
Wouter Cames van Batenburg, Samuel Korsky
For positive integers and , let be the maximum order of a graph of maximum degree at most and diameter at most . We prove that $$ \lim_{d\to\infty}\frac{n_k(…
Domination-packing ratio for planar and unit disk graphs
Wouter Cames van Batenburg
The domination number of a graph is the smallest possible size of a vertex set that intersects every radius- ball of , and the packing number is the maximum…
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…
Hat guessing with proper colorings
Sam Adriaensen, Peter Bentley, Anurag Bishnoi +6
We initiate the study of the hat guessing number of a graph where the adversary is only allowed to provide a proper coloring of the graph. This is the largest number for which…
Disjoint Correspondence Colorings for -Minor-free Graphs
Wouter Cames van Batenburg, Daniel W. Cranston, František Kardoš
Thomassen famously proved that every planar graph is 5-choosable. We explore variants of this result, focusing on finding disjoint correspondence colorings, in the more general cla…