On the Complexity of Planar Covering of Small Graphs

DOI10.1007/978-3-642-25870-1_9zbMath1341.05200arXiv1108.0064OpenAlexW1670213466WikidataQ62048093 ScholiaQ62048093MaRDI QIDQ3104767

No author found.

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

\(\operatorname{PlanarCover}(H)\) problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

3-connected reduction for regular graph covers ⋮ List covering of regular multigraphs ⋮ List covering of regular multigraphs with semi-edges

Cites Work

• The complexity of the \(L(p,q)\)-labeling problem for bipartite planar graphs of small degree
• On the complexity of H-coloring
• The spherical genus and virtually planar graphs
• Intersection graphs of curves in the plane
• Regular codes in regular graphs are difficult
• Intersection graphs of segments
• Covering regular graphs
• List-Coloring Squares of Sparse Subcubic Graphs
• On possible counterexamples to Negami's planar cover conjecture
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Complexity of Planar Covering of Small Graphs