Graph Covers

Abstract

Nakrytí je lokálně bijektivní homomorfismus z grafu A do souvislého grafu B. Ví- cenásobné hrany, smyčky a půlhrany jsou připouštěny, ale hypotéza Strong Dichotomy Conjecture tvrdí, že pro fixní souvislý graf H, výpočetní složitost otázky zda G nakrývá H je již plně určena jednoduchými grafy G. Následující kvaziuspořádání bylo zavedeno: Souvislý graf A je silnější než souvislý graf B, pokud každý jednoduchý graf G nakrývající A také nakrývá B. V roce 2022 Kratochvíl vyslovil hypotézu, že když A nemá půlhrany, pak A je silnější než B právě, když A nakrývá B. Kratochvíl a Nedela tuto hypotézu dokázali v případech kdy B je kubický graf na jednom vrcholu nebo A je dipól bez smyček a půlhran. My tuto relaci plně charakterizujeme pro A na jednom vrcholu, dipól bez půlhran, neregulární dipól a, částečně, obecný dipól. Tím pro tyto případy speciálně ověříme Kra- tochvílovu hypotézu. Nové metody jsou v průběhu vyvinuty a my představíme jejich důsledky pro počítání disjunktních perfektních párování v jednoduchých regulárních gra- fech.

A covering projection is a locally bijective homomorphism from a graph A to a con- nected graph B. Multiple edges, loops and semi-edges are considered but the Strong Dichotomy Conjecture asserts that for a fixed connected graph H, the complexity of de- termining whether G covers H is already dictated by simple graphs G. A quasi-order was introduced: A connected graph A is stronger than a connected graph B if every simple graph covering A also covers B. In 2022, Kratochvíl conjectured that if A has no semi-edges, then A is stronger than B iff A covers B. Kratochvíl & Nedela proved this conjecture when B is a cubic one-vertex graph, or A is a dipole with no loops and no semi-edges. We describe this relation fully for A being a one-vertex graph, a dipole with no semi- edges, an irregular dipole, and, partially, a general dipole. Consequently, we verify the conjecture in such cases. New methods are developed and their impact on counting disjoint perfect matchings in simple regular graphs is presented.