Trahtenbrot-Zykov problem and NP-completeness

DOI10.1016/0012-365X(92)90679-AMaRDI QIDQ1201257zbMATH OpenFDO

Authors Peter Bugata

Publication date 17 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)90679-A

zbMATH Keywords

NP-completenessunsolvabilitygraphs with given neighbourhoodsTrahtenbrot-Zykov problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• NP-completeness of graph decomposition problems
• Publication:3201758
• scientific article; zbMATH DE number 125451
• Complete problems for monotone NP
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs

Cites work

• scientific article; zbMATH DE number 125451 (Why is no real title available?)
• scientific article; zbMATH DE number 3641494 (Why is no real title available?)
• A polynomial time algorithm recognizing link trees
• On graphs with given environments of vertices

Cited in

(9)

• Tatamibari is NP-complete
• NP-completeness of the energy barrier problem without pseudoknots and temporary arcs
• The Complexity of Zadeh's Pivot Rule
• scientific article; zbMATH DE number 125451 (Why is no real title available?)
• Some locally Kneser graphs
• NP-completeness of the Hamming salesman problem
• NP-Completeness of the Direct Energy Barrier Problem without Pseudoknots
• On extremal sizes of locally \(k\)-tree graphs.
• scientific article; zbMATH DE number 5320331 (Why is no real title available?)

This page was built for publication: Trahtenbrot-Zykov problem and NP-completeness

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