Seminar of Graph Theory - Peter Zeman (12.12.2019)

Thursday 12.12.2019 at 9:50, Lecture room M/213

11. 12. 2019 07.42 hod.
By: Martin Škoviera

Peter Zeman (Faculty of Mathematics and Physics, Charles University, Prague):
On H-topological intersection graphs

Abstract:
Biró, Hujter, and Tuza (1992) introduced the concept of H-graphs, intersection graphs of connected subregions of a graph H thought of as a one-dimensional topological space. They relate to and generalize many important classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs.

Surprisingly, we negatively answer a 30-year-old question of Biró, Hujter, and Tuza which asks whether H-graphs can be recognized in polynomial time, for a fixed graph H. Moreover, our paper opens a new research area in the field of geometric intersection graphs by studying H-graphs from the point of view of fundamental computational problems of theoretical computer science: recognition, graph isomorphism, dominating set, clique, and colorability.

(joint work with: Steven Chaplick, Martin Töpfer, Jan Voborník)