Chromatic Number of the Alphabet Overlap Graph, G(2, k, k-2).

NEW

Problem: Let $A=\{0,1\}$. Reconstruct $G(2,8,6)$ as the simple finite alphabet-overlap graph with vertex set $A^8$, where two distinct words $x=x_1\cdots x_8$ and $y=y_1\cdots y_8$ are adjacent iff

Loops are omitted; otherwise the finite chromatic-number question would be ill-posed. This is the standard interpretation supported by the notation $G(2,k,k-2)$ and the thesis title.

Result:

Encode a word as an 8-bit integer $u$. Then adjacency is exactly

The following self-contained exact verifier proves both bounds: it checks the displayed 4-coloring and exhaustively proves non-3-colorability by backtracking after fixing a triangle’s colors.

T = """1000111111111111
0300000022222222
0000000000000000
0000000000000000
2222220022222222
1111232211111111
0000000000000000
0000000000000000
2222111122222222
1111212222222222
1311331122323111
1111232222332223
2222223322222222
1111212211111111
3333333322122111
1111333311332221""".split()

N = 256
S = [set() for _ in range(N)]
for u in range(N):
    for v in range(u + 1, N):
        if (u & 63) == (v >> 2) or (v & 63) == (u >> 2):
            S[u].add(v); S[v].add(u)
A = [sorted(s) for s in S]

# Verify the 4-coloring table.
C = [int(T[u >> 4][u & 15]) for u in range(N)]
assert all(C[u] != C[v] for u in range(N) for v in A[u] if u < v)

# Triangle used to break color symmetry.
assert all(v in A[u] for u, v in [(0, 1), (0, 64), (1, 64)])

def qcolorable(q):
    full = (1 << q) - 1
    col = [-1] * N
    avail = [full] * N
    U = set(range(N))

    def assign(v, c):
        b = 1 << c
        col[v] = c
        U.remove(v)
        ch = [(v, avail[v])]
        avail[v] = b
        ok = True
        for w in A[v]:
            if col[w] == c:
                ok = False; break
            if col[w] < 0 and (avail[w] & b):
                ch.append((w, avail[w]))
                avail[w] &= ~b
                if avail[w] == 0:
                    ok = False; break
        return ok, ch

    if q == 3:
        for v, c in [(0, 0), (1, 1), (64, 2)]:
            ok, _ = assign(v, c)
            if not ok:
                return False

    def dfs():
        if not U:
            return True
        v = max(U, key=lambda x: ((full ^ avail[x]).bit_count(), len(A[x]), -x))
        m = avail[v]
        while m:
            b = m & -m
            m -= b
            ok, ch = assign(v, b.bit_length() - 1)
            if ok and dfs():
                return True
            for w, old in reversed(ch):
                avail[w] = old
                if col[w] >= 0:
                    col[w] = -1
                    U.add(w)
        return False

    return dfs()

assert not qcolorable(3)
print("chi=4")

The pruning in qcolorable is only the necessary rule that adjacent vertices cannot share a color; hence the failed search exhausts all 3-colorings up to permutation of colors. The table gives $\chi\le4$, and the exhaustive failure gives $\chi\ge4$.

Citation: Problem source: Jerry Brent Farley, Chromatic Number of the Alphabet Overlap Graph, $G(2,k,k-2)$, East Tennessee State University master’s thesis, 2007, ETD 2130. No prior resolution is invoked here.