Complexity of dimension three and some related edge-covering characteristics of graphs

DOI10.1016/0304-3975(80)90039-0zbMath0442.68031OpenAlexW2109635482MaRDI QIDQ1143791

Jaroslav Nešetřil, Luděk Kučera, Ales Pultr

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90039-0

zbMATH Keywords

edge-covering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (6)

Note on strong product graph dimension ⋮ On the equivalence covering number of splitgraphs ⋮ Unnamed Item ⋮ On the dimension of trees ⋮ Matching relations and the dimensional structure of social choices ⋮ Induced Embeddings into Hamming Graphs.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of a graph
• On the computational power of pushdown automata
• The Complexity of Near-Optimal Graph Coloring
• On the Computational Complexity of Combinatorial Problems
• Reducibility among Combinatorial Problems
• The complexity of theorem-proving procedures
• Partially Ordered Sets

This page was built for publication: Complexity of dimension three and some related edge-covering characteristics of graphs