Block reduction conjecture for graph covers
Block reduction conjecture for graph covers
Let be a graph, and let be a block graph of , meaning a graph obtained from by replacing each block according to the block construction used in the paper. The problem asks whether a simple input graph admits a cover mapping to .
Block reduction conjecture. The problem for simple input graphs polynomially reduces to for simple input graphs.
The conjecture is proposed as a possible extension of the paper's reduction method and could help transfer complexity results between target graphs. The supplied context does not establish whether it has been proved or refuted.
Sources & referencesView supporting material
Primary source
Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl and Micheala Seifrtová, “Computational Complexity of Covering Colored Mixed Multigraphs with Simple Degree Partitions”, arXiv:2502.20151 (2025).
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.