Graph Ramsey theory and the polynomial hierarchy
From MaRDI portal
Publication:5943091
DOI10.1006/JCSS.2000.1729zbMath0986.05074OpenAlexW2125015388MaRDI QIDQ5943091
Publication date: 3 June 2002
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.2000.1729
Graph theory (including graph drawing) in computer science (68R10) Generalized Ramsey theory (05C55)
Related Items (8)
Inconsistency-tolerant query answering for existential rules ⋮ On the computational complexity and strategies of online Ramsey theory ⋮ On Ramsey-minimal infinite graphs ⋮ Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy ⋮ The complexity of reasoning with FODD and GFODD ⋮ On the complexity of core, kernel, and bargaining set ⋮ THE RAMSEY NUMBER FOR A LINEAR FOREST VERSUS TWO IDENTICAL COPIES OF COMPLETE GRAPHS ⋮ On Some Open Questions for Ramsey and Folkman Numbers
Cites Work
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory
- Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
- Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
- On the use of senders in generalized Ramsey theory for graphs
- The complexity of combinatorial problems with succinct input representation
- What can we hope to accomplish in generalized Ramsey theory ?
- Induced Ramsey numbers
- Generalized Ramsey theory for graphs. III: Small off-diagonal numbers
- Complexity Results for POMSET Languages
- Diagonal Ramsey numbers for small graphs
- Equivalences Among Relational Expressions with the Union and Difference Operators
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Graph Ramsey theory and the polynomial hierarchy
