Bounding the cop number of a graph by its genus


الملخص بالإنكليزية

It is known that the cop number $c(G)$ of a connected graph $G$ can be bounded as a function of the genus of the graph $g(G)$. The best known bound, that $c(G) leq leftlfloor frac{3 g(G)}{2}rightrfloor + 3$, was given by Schr{o}der, who conjectured that in fact $c(G) leq g(G) + 3$. We give the first improvement to Schr{o}ders bound, showing that $c(G) leq frac{4g(G)}{3} + frac{10}{3}$.

تحميل البحث