{
  "id": "1806.05286",
  "version": "v1",
  "published": "2018-06-13T22:10:53.000Z",
  "updated": "2018-06-13T22:10:53.000Z",
  "title": "Bounds on the localization number",
  "authors": [
    "Anthony Bonato",
    "William B. Kinnersley"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "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 $\\zeta (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 $\\zeta (G) \\le k$ has degeneracy less than $3^k$ and, consequently, satisfies $\\chi(G) \\le 3^{\\zeta (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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-13T22:10:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "localization number",
      "exploiting distance probes",
      "corresponding optimization parameter",
      "localization game",
      "cops attempt"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}