Trahtenbrot-Zykov problem and NP-completeness

DOI10.1016/0012-365X(92)90679-AzbMath0783.05076MaRDI QIDQ1201257

Peter Bugata

Publication date: 17 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completenessunsolvabilitygraphs with given neighbourhoodsTrahtenbrot-Zykov problem

Mathematics Subject Classification ID

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

Related Items (1)

On extremal sizes of locally k-tree graphs

Cites Work

• On graphs with given environments of vertices
• A polynomial time algorithm recognizing link trees
• Unnamed Item
• Unnamed Item

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