Hi, The Graph.is_chordal function can be used to return a chordless cycle on non-chordal graphs, but the implementation seems to be wrong.
Example (ran on the sagenb.org server): sage: g = Graph({3:[2,1,4],2:[1],4:[1],5:[2,1,4]}) sage: g.is_chordal() => False sage: _, g1 = g.is_chordal(certificate=True); g1.is_chordal() => True Currently, the function proceeds as follows: 1. run algorithm LexBFS to find a vertex ordering which would be a perfect-elimination-order (PEO) if G is chordal. 2. check if this ordering satisfies the PEO-property w.r.t. G, and if not, remember the last vertex (i) in the PEO which violates it. (assume G is not chordal) 3. let G' be the vertex induced subgraph of G corresponding to all vertices occuring after (i) in the PEO. 4. find two non-adj. vertices (j), (k) in G', which were both adj. to (i) in G. 5. find a shortest path between them in G', and return the vertex induced subgraph consisting of this path plus (i). The resulting cycle is not necessarily chordless, since the shortest path can contain another neighbour (x) of (i), resulting in the chord {x,i}. One linear-time solution is given in [1]. I think it is not hard to modify the code to use this. [1] Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. http://dx.doi.org/10.1137/0214020 Regards, Jan -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org