Covering regular graphs
From MaRDI portal
Publication:1386472
DOI10.1006/jctb.1996.1743zbMath0895.05049OpenAlexW1985986630MaRDI QIDQ1386472
Jan Arne Telle, Andrzej Proskurowski, Jan Kratochvíl
Publication date: 10 August 1998
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/539d53c1487858417d8106aa10456718387fef04
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (26)
Digital products, wedges, and covering spaces ⋮ 3-connected reduction for regular graph covers ⋮ List covering of regular multigraphs ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Locally injective \(k\)-colourings of planar graphs ⋮ Graph covers: where topology meets computer science, and simple means difficult ⋮ Comparing Universal Covers in Polynomial Time ⋮ List covering of regular multigraphs with semi-edges ⋮ Loose cover of graphs ⋮ Locally constrained graph homomorphisms and equitable partitions ⋮ Computing role assignments of proper interval graphs in polynomial time ⋮ Packing bipartite graphs with covers of complete bipartite graphs ⋮ Locally constrained graph homomorphisms -- structure, complexity, and applications ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism ⋮ Computing Role Assignments of Proper Interval Graphs in Polynomial Time ⋮ Complexity of Locally Injective Homomorphism to the Theta Graphs ⋮ Locally Injective Homomorphism to the Simple Weight Graphs ⋮ On the computational complexity of partial covers of theta graphs ⋮ Computing role assignments of chordal graphs ⋮ Fixed-parameter complexity of \(\lambda\)-labelings ⋮ Comparing universal covers in polynomial time ⋮ Upper bounds and algorithms for parallel knock-out numbers ⋮ Graph labelings derived from models in distributed computing: A complete complexity classification ⋮ On the Complexity of Planar Covering of Small Graphs ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree ⋮ A complete complexity classification of the role assignment problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of H-coloring
- Finite common coverings of pairs of regular graphs
- Isomorphisms and automorphisms of graph coverings
- Generating all graph coverings by permutation voltage assignments
- Coverings and minors: Application to local computations in graphs
- Homomorphisms of derivative graphs
- Homological Coverings of Graphs
- The NP-Completeness of Edge-Coloring
- `` Strong NP-Completeness Results
- NP completeness of finding the chromatic index of regular graphs
- Groups and Monoids of Regular Graphs (And of Graphs with Bounded Degrees)
This page was built for publication: Covering regular graphs
