The stronger-than relation conjecture for graphs without semi-edges

Let AA and BB be connected graphs. Write ABA\triangleright B when every simple graph that covers AA also covers BB, and write ABA\longrightarrow B when AA covers BB. A graph has no semi-edges if none of its edges is a semi-edge.

The stronger-than relation conjecture. If AA has no semi-edges, then

ABAB.A\triangleright B\quad\Longleftrightarrow\quad A\longrightarrow B.

This conjecture characterizes the stronger-than relation for graphs without semi-edges and would show that the apparently broader relation yields no additional comparisons in that case. It was formulated as an open conjecture in the GROW 2022 open problem session.

Sources & referencesView supporting material

Primary source

Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl and Michaela Seifrtová, “Computational Complexity of Covering Disconnected Multigraphs”, arXiv:2306.06431 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.