Cops and robbers on intersection graphs
Publication:1645059
DOI10.1016/j.ejc.2018.04.009zbMath1390.05145arXiv1607.08058WikidataQ62048086 ScholiaQ62048086MaRDI QIDQ1645059
Jan Kratochvíl, Vít Jelínek, Tomáš Gavenčiak, Przemysław Gordinowicz, Pavel Klavík
Publication date: 28 June 2018
Published in: European Journal of Combinatorics, Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.08058
games on graphs; intersection graphs; string graphs; cop number; pursuit games; cop and robber; interval filament graphs
91A43: Games involving graphs
91A24: Positional games (pursuit and evasion, etc.)
05C62: Graph representations (geometric and intersection representations, etc.)
05C57: Games on graphs (graph-theoretic aspects)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum weight independent sets and cliques in intersection graphs of filaments
- Triangle-free intersection graphs of line segments with large chromatic number
- The complexity of pursuit on a graph
- A game of cops and robbers
- Note on a pursuit game played on graphs
- A short note about pursuit games played on a graph with a given genus
- String graphs. II: Recognizing string graphs is NP-hard
- Intersection graphs of curves in the plane
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- Cops and robbers on intersection graphs
- Vertex-to-vertex pursuit in a graph
- On the computational complexity of a game of cops and robbers
- Cops and robbers is EXPTIME-complete
- Pursuing a fast robber on a graph
- Boxicity of graphs on surfaces
- A note on the cops and robber game on graphs embedded in non-orientable surfaces
- Cops and robbers playing on edges
- Cops and Robbers on Geometric Graphs
- Cops and Robbers on String Graphs
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- A Separator Theorem for String Graphs and Its Applications
- Graph Classes: A Survey
- Outerstring graphs are χ-bounded
- A better bound for the cop number of general graphs
- Topology of Thin Film RC Circuits
- Colouring arcwise connected sets in the plane. I