Graphs and complete intersection toric ideals
Our purpose is to study the family of simple undirected graphs whose toric ideal is a complete intersection from both an algorithmic and a combinatorial point of view. We obtain a polynomial time algorithm that, given a graph , checks whether its toric ideal is a complete intersection or not. Whenever is a complete intersection, the algorithm also returns a minimal set of generators of . Moreover, we prove that if is a connected graph and is a complete intersection, then there exist two induced subgraphs and of such that the vertex set of is the disjoint union of and , where is a bipartite ring graph and is either the empty graph, an odd primitive cycle, or consists of two odd primitive cycles properly connected. Finally, if is -connected and is connected, we list the families of graphs whose toric ideals are complete intersection.