mogirth5.sage

def girth5():
	"""
	search for 4 chromatic graph of girth at least 5
	http://mathoverflow.net/questions/193716/what-is-the-smallest-4-chromatic-graph-of-girth-5?noredirect=1#comment482350_193716
	requires optional package "nauty", install it with
	sage -i nauty
	usage
	%runfile mogirth5.sage
	girth5()


	DISCLAIMER:  no warranty of any kind ;)
	"""
	co=0
	F=[]
	M=10^4 #print stats at M graphs
	for n in [ 15 .. 21]: #range for orders
		print 'n=',n
		#  vvv nauty's options -t = triangle free, -f = 4 cycle free, -c = connected
		for g in graphs.nauty_geng("%s -c -t -f"%n):
			co += 1
			c=g.chromatic_number()
			if c>=4:
				F += [(c,g.graph6_string())]
				print ' found :-)',F
			#vvv probably should be commented for speed	
			if co%M==0:  print n,co,c,F #,g.girth()