CIO and ring graphs: Deficiency and testing

We give a polynomial time algorithm that tests whether a graph is a theta-ring graph or equivalently if a graph has the ∀θ∃Δ-property (each chorded-theta has a transversal triangle). It is known that G is a theta-ring graph if and only if G is a CIO graph (each toric ideal associated to an edge orientation of G is a binomial complete intersection). In particular ring graphs are theta-ring graphs. We prove that the forbidden induced subgraphs that characterize ring graphs are chorded-thetas and K4. We introduce a new graph invariant, the CIO deficiency. This invariant has the property that graphs with CIO deficiency zero are exactly CIO graphs.