论文标题
COP的图形数没有长孔
Cop number of graphs without long holes
论文作者
论文摘要
图中的一个洞是一个至少4个长度的诱发循环。我们为T-3警察提供了一种简单的获胜策略，以捕获强盗在警察和强盗游戏中捕获强盗，而抢劫者则在图中捕捉至少长度t的孔。这加强了Joret-Kaminski-Theis的定理，他证明T-2警察在此类图中具有获胜的策略。由于我们的界限，我们还给出了不平等的COP编号和图形的Dilworth数量。
A hole in a graph is an induced cycle of length at least 4. We give a simple winning strategy for t-3 cops to capture a robber in the game of cops and robbers played in a graph that does not contain a hole of length at least t. This strengthens a theorem of Joret-Kaminski-Theis, who proved that t-2 cops have a winning strategy in such graphs. As a consequence of our bound, we also give an inequality relating the cop number and the Dilworth number of a graph.
