color3.sage

def chromaticpolymodx3optm(g,prot=False):
	"""
	decides if $g$ is 3-colorable using the chromatic
	polynomial mod x-3
	
	g: graph
	prot:  verbose
	returns 0 iff g is not 3-colorable
	License: GPL 3.0
	Author:  joro
	tested on sage 6.2
	sample usage:
	  sage: %runfile color3.sage
	  sage: lp=graphs.RandomRegular(3,100).line_graph()
	  sage: time p3=chromaticpolymodx3optm(lp,1)
	  sage: p3

	"""
	fast=True
	g=g.copy()
	g.relabel()

	Z1.<x>=ZZ[]
	zero=Z1(0)
	K4=graphs.CompleteGraph(4)
	K4m=Graph(K4)
	K4m.delete_edge(K4m.edges()[0])
	
	good=x**20
	D=10

	global cou,dr
	cou=0
	dr=0
	def isfree(g,f):
		"""
		g is f-free
		"""
		return g.subgraph_search(f,induced=True) is None

	def rec(g,prot=False):
		##print 'rec',g
		global cou,dr
		if fast and not isinstance(g,Graph) and g.degree()>=D:  return g

		cou += 1
		if prot:  print ' #',cou,dr,'g=',g.num_verts() #,g.sparse6_string()
		if not g.is_connected():
			if prot:
				print 'disconnected'
		        return prod([rec(g,prot=prot) for g in G.connected_components_subgraphs()])
		if g.subgraph_search(K4) is not None:
			if prot:  print 'K_4'
			return zero

		if g.is_clique():
			n=g.num_verts()
			if prot:
				if n<=3:  print 'clique ',n
			if n>=4:  return zero	
			p=prod([x-i for i in [0 .. n - 1]])
			if n<=3 and fast:  return good
			return p
		##if not islocallybipartite(g):
		##	if prot:  print 'not locally bipartite'
		##	return zero

		G=g.copy()

		while True:
			f=G.subgraph_search(K4m,induced=True)
			if f is None:  break
			ve=[i for i in f.vertices() if f.degree(i)==2]
			u,v=ve
			if prot:  print 'K_4 edge'
			G.merge_vertices([u,v])
			if not isfree(G,K4):
				if prot:  print 'K_4 from diamond removal'
				return zero
			if G.is_clique():
				if prot:  print 'clique from diamond removal'
				return rec(G,prot=prot)
	
		g=G	
		"""		
		for u,v in ed:
			G=g.copy()
			G.merge_vertices([u,v])
			##print '  ',u,v
			if G.subgraph_search(K4) is not None:
				if prot:  print 'K_4 merge'
				G=g.copy()
				G.add_edge(u,v)
				return rec(G,prot=prot)
		"""		

		u,v=g.complement().edges(labels=False)[0] #XXX
		if prot:
			print 'dob rec'
		dr += 1	

		g1=g.copy()
		g2=g.copy()
		g1.add_edge(u,v)
		g2.merge_vertices([u,v])
		t1=rec(g1,prot=prot)
		if fast and t1.degree()>D:  return good
		t2=rec(g2,prot=prot)
		if fast and t2.degree()>D:  return good
		return t1+t2
	p=rec(g,prot=prot)
	if prot:  print ' steps=',cou,'double=',dr
	return p