coloring_graph.py

def k_subset(s, k):
    if k == len(s):
        return (tuple([(x,) for x in s]),)
    k_subs = []
    for i in range(len(s)):
        partials = k_subset(s[:i] + s[i + 1:], k)
        for partial in partials:
            for p in range(len(partial)):
                k_subs.append(partial[:p] + (partial[p] + (s[i],),) + partial[p + 1:])
    return k_subs

def uniq_subsets(s):
    u = set()
    for x in s:
        t = []
        for y in x:
            y = list(y)
            y.sort()
            t.append(tuple(y))
        t.sort()
        u.add(tuple(t))
    return u

x=[1,2,3,4,5,6,7]
p=list(uniq_subsets(k_subset(x, i)) for i in range(1,len(x)+1))
r=[(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(2,5),(2,7),(3,4),(3,6),(3,7),(4,5),(4,6),(5,6),(5,7),(6,7)]

answer = []

for p_i in p:
	for p_i_method in p_i:
		#print('p_i_method',p_i_method)
		for p_i_n in p_i_method:
			#print('p_i_n',p_i_n)
			flag = True
			for rr in r:
				if rr[0] in p_i_n and rr[1] in p_i_n:
					flag = False
					break
			if not flag:
				break
		#print(flag)
		if flag:
			answer.append(p_i_method)

for ans in answer:
	print(ans)

output

$ python coloring_graph.py                                                                               
((1, 6), (2,), (3, 5), (4, 7))
((1,), (2, 6), (3, 5), (4, 7))
((1, 5), (2, 6), (3,), (4, 7))
((1, 6), (2,), (3, 5), (4,), (7,))
((1, 5), (2,), (3,), (4, 7), (6,))
((1,), (2, 6), (3,), (4, 7), (5,))
((1, 6), (2,), (3,), (4, 7), (5,))
((1, 5), (2, 6), (3,), (4,), (7,))
((1,), (2, 6), (3, 5), (4,), (7,))
((1,), (2,), (3, 5), (4, 7), (6,))
((1,), (2, 6), (3,), (4,), (5,), (7,))
((1, 5), (2,), (3,), (4,), (6,), (7,))
((1,), (2,), (3,), (4, 7), (5,), (6,))
((1, 6), (2,), (3,), (4,), (5,), (7,))
((1,), (2,), (3, 5), (4,), (6,), (7,))
((1,), (2,), (3,), (4,), (5,), (6,), (7,))