REVIEW 1 cited by
Cop number of graphs without long holes
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
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.
Forward citations
Cited by 1 Pith paper
-
$4K_1$-free graph with the cop number $3$
A 16-vertex graph, the complement of the Shrikhande graph, is claimed to have cop number 3 while being 4K1-free and Cℓ-free for all ℓ≥6, refuting Sivaraman's conjecture.
Discussion (0). Continue with ORCID to comment.