Seminar of Graph Theory - Roman Nedela (16.3.2023)
Thursday 16.3.2023 at 9:50, Lecture room M/213
Roman Nedela (Mathematical Institute SAS Bratislava):
Covers and semicovers between graphs: Who is stronger?
Abstract:
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)