Premium
Bounds on the localization number
Author(s) -
Bonato Anthony,
Kinnersley William B.
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22546
Subject(s) - degeneracy (biology) , combinatorics , mathematics , conjecture , chromatic scale , upper and lower bounds , hypercube , graph , discrete mathematics , constant (computer programming) , computer science , mathematical analysis , bioinformatics , biology , programming language
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 as ζ ( G ). We settle a conjecture of Bosek et al by providing an upper bound on the chromatic number as a function of the localization number. In particular, we show that every graph with ζ ( G ) ≤ k has degeneracy less than 3 k and, consequently, satisfies χ ( G ) ≤ 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.