The stronger-than relation conjecture for graphs without semi-edges
The stronger-than relation conjecture for graphs without semi-edges
Let and be connected graphs. Write when every simple graph that covers also covers , and write when covers . A graph has no semi-edges if none of its edges is a semi-edge.
The stronger-than relation conjecture. If has no semi-edges, then
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.