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

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

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

(20)

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

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)