Block reduction conjecture for graph covers

Let HH' be a graph, and let HH be a block graph of HH', meaning a graph obtained from HH' by replacing each block according to the block construction used in the paper. The problem \scH-Cover{\sc H\text{-}Cover} asks whether a simple input graph admits a cover mapping to HH.

Block reduction conjecture. The problem \scH-Cover{\sc H\text{-}Cover} for simple input graphs polynomially reduces to \scH-Cover{\sc H'\text{-}Cover} 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

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.