Cops and Robbers on intersection graphs
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10384801" target="_blank" >RIV/00216208:11320/18:10384801 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1016/j.ejc.2018.04.009" target="_blank" >https://doi.org/10.1016/j.ejc.2018.04.009</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ejc.2018.04.009" target="_blank" >10.1016/j.ejc.2018.04.009</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Cops and Robbers on intersection graphs
Popis výsledku v původním jazyce
The cop number of a graph G is the smallest k such that k cops win the game of cops and robber on G. We investigate the maximum cop number of geometric intersection graphs, which are graphs whose vertices are represented by geometric shapes and edges by their intersections. We establish the following dichotomy for previously studied classes of intersection graphs: The intersection graphs of arc-connected sets in the plane (called string graphs) have cop number at most 15, and more generally, the intersection graphs of arc-connected subsets of a surface have cop number at most 10g + 15 in case of orientable surface of genus g, and at most 10g' + 15 in case of non-orientable surface of Euler genus g'. For more restricted classes of intersection graphs, we obtain better bounds: the maximum cop number of interval filament graphs is two, and the maximum cop number of outer-string graphs is between 3 and 4. The intersection graphs of disconnected 2-dimensional sets or of 3-dimensional sets have unbounded cop number even in very restricted settings. For instance, it follows from known results that the cop number is unbounded on intersection graphs of two-element subsets of a line. We further show that it is also unbounded on intersection graphs of 3-dimensional unit balls, of 3-dimensional unit cubes or of 3-dimensional axis-aligned unit segments.
Název v anglickém jazyce
Cops and Robbers on intersection graphs
Popis výsledku anglicky
The cop number of a graph G is the smallest k such that k cops win the game of cops and robber on G. We investigate the maximum cop number of geometric intersection graphs, which are graphs whose vertices are represented by geometric shapes and edges by their intersections. We establish the following dichotomy for previously studied classes of intersection graphs: The intersection graphs of arc-connected sets in the plane (called string graphs) have cop number at most 15, and more generally, the intersection graphs of arc-connected subsets of a surface have cop number at most 10g + 15 in case of orientable surface of genus g, and at most 10g' + 15 in case of non-orientable surface of Euler genus g'. For more restricted classes of intersection graphs, we obtain better bounds: the maximum cop number of interval filament graphs is two, and the maximum cop number of outer-string graphs is between 3 and 4. The intersection graphs of disconnected 2-dimensional sets or of 3-dimensional sets have unbounded cop number even in very restricted settings. For instance, it follows from known results that the cop number is unbounded on intersection graphs of two-element subsets of a line. We further show that it is also unbounded on intersection graphs of 3-dimensional unit balls, of 3-dimensional unit cubes or of 3-dimensional axis-aligned unit segments.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2018
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
European Journal of Combinatorics
ISSN
0195-6698
e-ISSN
—
Svazek periodika
72
Číslo periodika v rámci svazku
August 2018
Stát vydavatele periodika
GB - Spojené království Velké Británie a Severního Irska
Počet stran výsledku
25
Strana od-do
45-69
Kód UT WoS článku
000437075300004
EID výsledku v databázi Scopus
2-s2.0-85046652151