From the 1 of 11 linked papers with an AI index.
11 papers
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 paper proves that the domination number is at most five times the packing number for any planar graph and at most about 9.924 times for any unit disk graph, improving previous…
On the chromatic number of the union of comparability graphs
Maria Chudnovsky, Wouter Cames van Batenburg, 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 cliq…
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…
The chromatic number of finite projective spaces
Anurag Bishnoi, Wouter Cames van Batenburg, Ananthakrishnan Ravi
The chromatic number of the finite projective space , denoted , is the minimum number of colors needed to color its points so that no line is monochrom…
Fractional list packing for layered graphs
Stijn Cambie, Wouter Cames van Batenburg
The fractional list packing number of a graph is a graph invariant that has recently arisen from the study of disjoint list-colourings. It measures how…