CIO and ring graphs: deficiency and testing (Q507135)

Each simple graph has a canonical edge orientation whose associated toric ideal is a complete intersection, see \textit{I. Gitler} et al. [Discrete Math. 310, 430--441 (2010; Zbl 1198.05089)]. On the other hand, there exist some graphs whose toric ideals associated to any edge orientation are complete intersections. These graphs are called CIO graphs (Complete Intersection for each edge Orientation). In their previous work, the authors [J. Algebr. Comb. 38, No. 3, 721--744 (2013; Zbl 1328.05202)] gave a combinatorial characterization for CIO graphs by showing that CIO graphs are the theta-ring graphs in which each chorded-theta has a transversal triangle, where a chorded-theta is the subgraph induced by three disjoint paths between two nonadjacent vertices and a transversal triangle is a triangle meeting exactly one internal vertex of each of these three paths. \textit{I. Bermejo} and \textit{I. Garc.a-Marco} [J. Symb. Comput. 68, 265--286 (2015; Zbl 1311.13024)] gave a polynomial-time algorithm to check the complete intersection property for toric ideals associated to graphs. The authors give a polynomial-time algorithm to test whether a graph is a theta-ring graph or equivalently each chorded theta has a transversal triangle. They also prove that the forbidden induced subgraphs that characterize ring graphs are chorded-thetas and the complete graph on four vertices.