List covering of regular multigraphs

DOI10.1007/978-3-031-06678-8_17MaRDI QIDQ2169958zbMATH OpenOpenAlexFDO

Authors Jan Bok, Nikola Jedličková, Jan Kratochvíl, Jiří Fiala, Paweł Rzążewski

Publication date 30 August 2022

Full work available at URL https://arxiv.org/abs/2204.04280

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• 3-connected reduction for regular graph covers
• A complete complexity classification of the role assignment problem
• Algebraic Graph Theory
• Algorithmic aspects of regular graph covers with applications to planar graphs
• Antipodal covering graphs
• Automorphisms of graphs and coverings
• Complexity of locally-injective homomorphisms to tournaments
• Computational complexity of covering disconnected multigraphs
• Computational complexity of covering three-vertex multigraphs
• Covering regular graphs
• Elementary abelian covers of graphs
• Finite common coverings of graphs
• Generating all graph coverings by permutation voltage assignments
• Harmonic morphisms of graphs. Part I: Graph coverings
• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 1236360 (Why is no real title available?)
• scientific article; zbMATH DE number 1107736 (Why is no real title available?)
• scientific article; zbMATH DE number 2080268 (Why is no real title available?)
• scientific article; zbMATH DE number 2081019 (Why is no real title available?)
• scientific article; zbMATH DE number 3450230 (Why is no real title available?)
• scientific article; zbMATH DE number 2111730 (Why is no real title available?)
• scientific article; zbMATH DE number 7724194 (Why is no real title available?)
• Labelling Graphs with a Condition at Distance 2
• Lifting graph automorphisms by voltage assignments
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• Modular operads
• NP completeness of the edge precoloring extension problem on bipartite graphs
• On the complexity of planar covering of small graphs
• Partial covers of graphs
• Regular embeddings of canonical double coverings of graphs
• Revisiting Leighton’s theorem with the Haar measure
• Subexponential algorithms for variants of the homomorphism problem in string graphs

Cited in

(8)

• Graph covers: where topology meets computer science, and simple means difficult
• List covering of regular multigraphs with semi-edges
• List covering of regular multigraphs with semi-edges
• Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
• An algorithmic framework for locally constrained homomorphisms
• Computational complexity of covering multigraphs with semi-edges: small cases
• Graph covers and generalized snarks (extended abstract)
• Computational complexity of covering regular trees

This page was built for publication: List covering of regular multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2169958)