Hi Nathann,
First, thank you for taking time to give a very detailed reply.
I'm sorry but I'm not yet done bothering you :-]
I think this is wrong:
> When v is considered for removal, it is a leaf of the lex-BFS tree.
> Its father (and first discoverer) is named x, and we suppose that
> there is a vertex y which is not a neighbor of x, otherwise v is
> removed without any problem.
(I also mentioned this in message #3, but it seems it still holds)
Consider: g = graph({1:[2,3,4,5],2:[3,5],4:[3,5]}).
g is like [the 4-cycle 2--3--4--5] + [(1,x) for x in [2 .. 5]]
g is not chordal.
A LexBFS ordering (reverse elimination ordering) could be [1, 2, 3, 5,
4].
Notice that all v in [2 .. 5] have father equal to 1.
But then x is adjacent to every other vertex, i.e. we can't find y.
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
