Subgraphs and Colourability of Locatable Graphs
From MaRDI portal
Abstract: We study a game of pursuit and evasion introduced by Seager in 2012, in which a cop searches the robber from outside the graph, using distance queries. A graph on which the cop wins is called locatable. In her original paper, Seager asked whether there exists a characterisation of the graph property of locatable graphs by either forbidden or forbidden induced subgraphs, both of which we answer in the negative. We then proceed to show that such a characterisation does exist for graphs of diameter at most 2, stating it explicitly, and note that this is not true for higher diameter. Exploring a different direction of topic, we also start research in the direction of colourability of locatable graphs, we also show that every locatable graph is 4-colourable, but not necessarily 3-colourable.
This page was built for publication: Subgraphs and Colourability of Locatable Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6248983)
