|
| |
|
|
Structural and complexity questions of graph theory
Gavenčiak, Tomáš ; Kratochvíl, Jan (advisor) ; Hliněný, Petr (referee) ; Fomin, Fedor (referee)
DOCTORAL THESIS ABSTRACT Tomáš Gavenčiak Structural and complexity questions of graph theory The original cops and robber game, proposed in 1983 by Nowakowski and Winkler, and independently by Quilliot, is a two-player combinatorial pursuit game on a graph. Many related games have been introduced and studied since then, both with a purely game theoretic motivation and for their applications in graph theory and connections with graph width parameters. We give an overview of the field and present three particular results: We show bounds on the required number of cops for various connected intersection graph classes, most notably we show that on connected string graphs 15 cops always win. We show the game of cops and fast robber to be polynomially decidable on interval graphs and as a tool we generalise the problem of defensive domination and show a polynomial algorithm for interval graphs. Finally we propose and examine generalisations of tree-depth, marshals and robber games, and minors to hypergraphs and hypergraph pairs.
|
|
| |
|
|
Structural and complexity questions of graph theory
Gavenčiak, Tomáš ; Kratochvíl, Jan (advisor) ; Hliněný, Petr (referee) ; Fomin, Fedor (referee)
DOCTORAL THESIS ABSTRACT Tomáš Gavenčiak Structural and complexity questions of graph theory The original cops and robber game, proposed in 1983 by Nowakowski and Winkler, and independently by Quilliot, is a two-player combinatorial pursuit game on a graph. Many related games have been introduced and studied since then, both with a purely game theoretic motivation and for their applications in graph theory and connections with graph width parameters. We give an overview of the field and present three particular results: We show bounds on the required number of cops for various connected intersection graph classes, most notably we show that on connected string graphs 15 cops always win. We show the game of cops and fast robber to be polynomially decidable on interval graphs and as a tool we generalise the problem of defensive domination and show a polynomial algorithm for interval graphs. Finally we propose and examine generalisations of tree-depth, marshals and robber games, and minors to hypergraphs and hypergraph pairs.
|
guest ::
