Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4946011 | Journal of Symbolic Computation | 2017 | 20 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Isidoro Gitler, Enrique Reyes, Juan A. Vega,