Graph Ramsey Theory and the Polynomial Hierarchy

摘要

In the Ramsey theory of graphs F→(G, H) means that for every way of coloring the edges of F red and blue F will contain either a red G or a blue H. Arrowing, the problem of deciding whether F→(G, H), lies in Πp2=coNPNP and it was shown to be coNP-hard by Burr [Bur90]. We prove that Arrowing is Πp2-complete, simultaneously settling a conjecture of Burr and providing a rare natural example of a problem complete for a higher level of the polynomial hierarchy. We also show that Strong Arrowing, the induced subgraph version of Arrowing, is Πp2-complete, and that the complexity of not arrowing stars is the same as that of finding a perfect matching.