Cops and robbers on intersection graphs

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

zbMATH Keywords

games on graphs; intersection graphs; string graphs; cop number; pursuit games; cop and robber; interval filament graphs

Mathematics Subject Classification ID

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

On Strict (Outer-)Confluent Graphs, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Cops and robbers on intersection graphs, Cops and robbers on directed and undirected abelian Cayley graphs, Chasing a drunk robber in many classes of graphs, On strict (outer-)confluent graphs

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