id	summary	reporter	owner	description	type	status	priority	milestone	component	resolution	keywords	cc	work_issues	upstream	reviewer	author	merged	dependencies	stopgaps
11735	Bug in is_chordal	ncohen	tbd	"As reported by Jan on sage-devel [1], the current implementation of is_chordal is incorrect. Given a vertex v adjacent to x and y (x and y being non-adjacent), a shortest path between x and y in G-v does not necessarily avoid the neighbors of v. Clearly.
Well, with this patch the shortest path is computed in the graph G with v and all its neighbors removed with the exception of x and y, so that it can not happen again.

Besides, as it is almost free to check that the certificate is indeed a hole, this patch adds a test just in case `:-)`

Nathann

Requires : 
   * #11738
Apply:
   * [attachment:trac_11735.patch]

[1] https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion"	defect	closed	major	sage-4.8	graph theory	fixed		lsampaio ddestrada dcoudert		N/A	David Coudert	Nathann Cohen	sage-4.8.alpha4