Bounds on the localization number

We consider the localization game played on graphs, wherein a set of cops attempt to determine the exact location of an invisible robber by exploiting distance probes. The corresponding optimization parameter for a graph $G$ is called the localization number and is written $ζ(G)$. We settle a conjecture of \cite{nisse1} by providing an upper bound on the localization number as a function of the chromatic number. In particular, we show that every graph with $ζ(G) \le k$ has degeneracy less than $3^k$ and, consequently, satisfies $χ(G) \le 3^{ζ(G)}$. We show further that this degeneracy bound is tight. We also prove that the localization number is at most 2 in outerplanar graphs, and we determine, up to an additive constant, the localization number of hypercubes.

No reviews yet.

No comments yet.