Different perspectives on graph homomorphism problems

Abstract

Homomorfizmy grafov (zobrazenia zachovávajúce susednosti medzi vrcholmi zdrojového a ciel'ového grafu) predstavujú jeden zo základných konceptov teórie grafov. Tento koncept vytvára most medzi zdanlivo odlišnými štruktúrami gra- fov a zohráva kl'účovú úlohu pri riešení širokej škály problémov v teórii grafov aj mimo nej. Táto práca skúma tri odlišné problémy, každý z nich úzko súvisí s problémom grafového homomorfizmu. Najprv skúmame výpočetnú zložitost ' hl'adania Hamiltonovskej cesty a kružnice v grafoch s obmedzenou nezávislost 'ou. Klasifikujeme zložitost ' týchto problémov všeobecne pre grafy s obmedzenou nezávislost 'ou, pričom ukazujeme, že oba problémy patria do triedy XP, ked' sú parametrizované nezávislost 'ou vstupného grafu. Ďalej sa zameriame na novo predstavený problém nazvaný Hamiltonian- `-Linkage, ktorý súvisí s pokrytím grafu cestami. Identifikujeme explicitné prekážky pre existenciu Hamiltonovskej cesty pre grafy s malou nezávislost 'ou. Problémy Hamiltonovskej cesty a pokrytia grafu cestami pre grafy s obmedze- nou nezávislost 'ou úzko súvisia s lokálne injektívnymi homomorfizmami. Ďalej skúmame zložitost ' problému listového homomorfizmu pre signed grafy. Zatial' čo zložitost ' problému bez...

Graph homomorphisms (being adjacency preserving mappings between vertices of graphs) are a fundamental concept in graph theory, providing a powerful framework for relating different graphs while preserving some of their struc- tural properties. The concept bridges the gap between seemingly distinct graph structures and plays a crucial role in solving a wide variety of problems in graph theory and beyond. This thesis explores three distinct problems, each rooted in the graph homomorphism framework. First, we study the computational complexity of finding a Hamiltonian path and cycle in graphs with bounded independence number. We classify the complexity of these problems in the general setting of graphs with bounded independence number, showing that both problems belong to the class XP when parameterized by the independence number of the input graph. We consider a newly introduced problem called Hamiltonian-`-Linkage, which is related to the notions of path covers and linkages in graphs. We also identify explicit obstacles to the existence of Hamiltonian paths for small values of k. The Hamiltonian path and path cover problems in graphs with a bounded independence number are closely related to locally injective homomorphisms. Next, we investigate the complexity of list homomorphism problems for...