Seminár z teórie grafov - Roman Nedela (16.3.2023)

vo štvrtok 16.3.2023 o 9:50 hod. v miestnosti M/213

13. 03. 2023 19.19 hod.
Od: Martin Škoviera

Prednášajúci: Roman Nedela (Matematický ústav SAV Bratislava)

Názov: Covers and semicovers between graphs: Who is stronger?

Termín: 16.3.2023, 9:50 hod., M 213

A graph A is called stronger than a graph B if every simple graph that covers A also covers B. This notion was defined and found useful for NP-hardness reductions for disconnected graphs. Kratochvil conjectured that if $A$ has no semi-edges, then $A$ is stronger than $B$ if and only if $A$ covers $B$. We prove this conjecture for cubic one-vertex graphs, and we also justify it for all cubic graphs $A$ with at most 4 vertices.

(Joint work with J. Kratochvil)

Stránka seminára