Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Graph Theory - Roman Nedela (16.3.2023)

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

13. 03. 2023 19.25 hod.
By: Martin Škoviera

Roman Nedela (Mathematical Institute SAS Bratislava):
Covers and semicovers between graphs: Who is stronger?

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)

More information