scientific article; zbMATH DE number 4178769

MaRDI QIDQ3201758zbMATH OpenFDO

Authors Stefan A. Burr

Publication date 1990

zbMATH Keywords

NP-complete problemRamsey-type problems

Mathematics Subject Classification ID

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

Recommendations

• Graph Ramsey theory and the polynomial hierarchy
• scientific article; zbMATH DE number 3889547
• scientific article; zbMATH DE number 3906534
• Graph Ramsey theory and the polynomial hierarchy
• Some undecidable problems involving the edge-coloring and vertex-coloring of graphs

Cited in

(16)

• Graph Ramsey theory and the polynomial hierarchy
• The complexity of \((P_k, P_\ell ) \)-arrowing
• Trahtenbrot-Zykov problem and NP-completeness
• Complexity of Computing the Anti-Ramsey Numbers for Paths.
• Co-Nondeterminism in Compositions
• The complexity of generalized graph colorings
• A packed Ramsey’s theorem and computability theory
• On the use of senders in generalized Ramsey theory for graphs
• Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
• scientific article; zbMATH DE number 3906534 (Why is no real title available?)
• What can we hope to accomplish in generalized Ramsey theory ?
• On Ramsey \((4K_2,P_3)\)-minimal graphs
• Complexity of computation of some functions of graphs
• Graph Ramsey theory and the polynomial hierarchy
• scientific article; zbMATH DE number 549852 (Why is no real title available?)
• On the combination of the Bernays-Schönfinkel-Ramsey fragment with simple linear integer arithmetic

This page was built for publication:

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