Graph Ramsey theory and the polynomial hierarchy

Summary form only given, as follows. 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 as a subgraph. The problem ARROWING of deciding whether F→(G, H) lies in Π₂^P=coNP^NP and it was shown to be coNP-hard by S.A. Burr (1990). We prove that ARROWING is actually Π ₂^P-complete, simultaneously settling a conjecture of Burr and providing a natural example of a problem complete for a higher level of the polynomial hierarchy. We also consider several specific variants of ARROWING, where G and H are restricted to particular families of graphs. We have a general completeness result for this case under the assumption that certain graphs are constructible in polynomial time. Furthermore we show that STRONG ARROWING, the version of ARROWING for induced subgraphs, is Π₂^P-complete