Réunion d'hiver SMC 2026
Montréal, 11 - 14 décembre 2026
Processus en temps discret sur les graphes
Org: Nancy E. Clarke (Acadia University), Alexander Clow (Simon Fraser University) et Erin Meger (Queens University)
Org: Nancy E. Clarke (Acadia University), Alexander Clow (Simon Fraser University) et Erin Meger (Queens University)
- CAELAN ATAMANCHUK, McGill University
- ANDREA BURGESS, University of New Brunswick
- MACKENZIE CARR, Toronto Metropolitan University
- NANCY CLARKE, Acadia University
- ALEXANDER CLOW, Simon Fraser University
The Hole Story for Cop Number [PDF]
- ANDREA BURGESS, University of New Brunswick
-
The cop number of a graph,
written $c(G)$,
is a central invariant in the study of discrete-time processes on graphs.
One advantage of cop number is its deep and well documented connection
to concepts in structural graph theory, such as graph minors, subgraphs, and induced subgraphs.
This talk will survey recent work on
the connection between cop number and the structure of holes in a graph.
A hole is an induced cycle of length at least $4$.
In doing so
we will show that any graph $G$ with $c(G) = \theta(G)=k\geq 2$,
where $\theta(G)$ is the clique cover number,
has $C_\ell$ as an induced subgraph for all $3\leq \ell \leq k+1$.
We will also prove that in any graph without holes of length at most $t$,
$N[P]$ can be guarded by $1$ cop for any short (as a function of $t$) induced path $P$,
even when $P$ is not a shortest path.
- JULIEN CODSI, Princeton University
- WILLIAM KELLOUGH, Memorial University
- ERIN MEGER, Queen's University
- PAWEL PRALAT, Toronto Metropolitan University
- BEN SEAMONE, Universite de Montreal
- WILLIAM KELLOUGH, Memorial University