CIO and ring graphs: deficiency and testing
type: Item
instance of: scholarly article
title: CIO and ring graphs: deficiency and testing
zbMATH Open document ID: 1365.05299
author: Isidoro Gitler
author: Enrique Reyes
author: Juan Antonio Vega
published in: Journal of Symbolic Computation
publication date: 2017-02-03T00:00:00Z
review text: 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.
reviewed by: Fatemeh Mohammadi
Mathematics Subject Classification ID: 05E15
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 6680370
zbMATH Keywords: complete intersection toric ideals
zbMATH Keywords: oriented graphs
zbMATH Keywords: prisms
zbMATH Keywords: pyramids
zbMATH Keywords: thetas
zbMATH Keywords: ring graphs
zbMATH Keywords: chorded-thetas
describes a project that uses: cisimplicial
MaRDI profile type: Publication
full work available at URL: j.jsc.2016.02.007
OpenAlex ID: W2307394146
cites work: When the unit, unitary and total graphs are ring graphs and outerplanar
cites work: When the comaximal and zero-divisor graphs are ring graphs and outerplanar
cites work: PLANAR, OUTERPLANAR, AND RING GRAPH OF THE COZERO-DIVISOR GRAPH OF A FINITE COMMUTATIVE RING
cites work: Complete intersections in simplicial toric varieties
cites work: Graphs and complete intersection toric ideals
cites work: An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection
cites work: Complete intersections in affine monomial curves
cites work: The toric ideal of a graphic matroid is generated by quadrics
cites work: Complete intersections in toric ideals
cites work: Detecting a Theta or a Prism
cites work: The three-in-a-tree problem
cites work: Toric varieties
cites work: Affine semigroup rings that are complete intersections
cites work: Implosive graphs: Square-free monomials on symbolic Rees algebras
cites work: Complete intersection toric ideals of oriented graphs and chorded-theta subgraphs
cites work: Ring graphs and complete intersection toric ideals
cites work: Q4979094
cites work: Combinatorial degree bound for toric ideals of hypergraphs
cites work: Generators and relations of abelian semigroups and semigroup rings
cites work: On the binomial arithmetical rank of toric ideals
cites work: Bipartite graphs whose edge algebras are complete intersections
cites work: Detecting induced subgraphs
cites work: Complete intersection vanishing ideals on degenerate tori over finite fields
cites work: Algorithms for Perfectly Contractile Graphs
cites work: On the geometry of complete intersection toric varieties
cites work: Complete intersection lattice ideals
cites work: Properties of cut ideals associated to ring graphs
cites work: Toric algebra of hypergraphs
cites work: Minimal generators of toric ideals of graphs
cites work: On regular sequences of binomials
cites work: On the jacobian module associated to a graph
cites work: On the universal Gröbner bases of toric ideals of graphs
cites work: On complete intersection toric ideals of graphs
cites work: Q4528984
DOI: 10.1016/J.JSC.2016.02.007
description: scientific article; zbMATH DE number 6680370