Graph Ramsey theory and the polynomial hierarchy
Marcus Schaefer · 1999
In the Ramsey theory ofgraphs 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.The problem ARROWING of deciding whether F + (G, H) lies in II; = coNPNP and it was shown to be coNP hard by Burr [5].We prove that ARROWING is actually II;-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 show that STRONG ARROWING, the version for induced subgraphs, is rI;-complete.