This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
For n=6, consider the graph C_6^(3), constructed as follows:
- Start with a cycle graph (hexagon) having vertices labeled {0,1,2,3,4,5}.
- Add chords connecting vertex i with vertex i+3 mod 6, forming edges (0,3), (1,4), (2,5).
- Since n is even, include diametric edges connecting opposite vertices: edges (0,3), (1,4), (2,5). (Note these diametric edges coincide with chords for n=6.)
The resulting graph is symmetric and moderately dense. Enumerating explicitly all possible vertex-coloring assignments with exactly three colors, we find precisely 42 distinct valid 3-colorings (each satisfying the condition that no two adjacent vertices share the same color).
Thus, a(6)=42.
with(GraphTheory):
Cn3_graph := proc(n)
local G, i;
G := CycleGraph(n);
for i from 0 to n-1 do
AddEdge(G, {i, (i+3) mod n});
end do;
if modp(n, 2) = 0 then
for i from 0 to n/2 - 1 do
AddEdge(G, {i, (i + n/2) mod n});
end do;
end if;
return G;
end proc:
a := proc(n) local G;
G := Cn3_graph(n);
return ChromaticPolynomial(G, 3);
end proc:
# Compute initial terms from n=6 to n=20:
seq(a(n), n=6..20);
Cn3Graph[n_] := Module[{g, edges, i},
edges = Table[{i, Mod[i + 1, n]}, {i, 0, n - 1}]; (* Cycle edges *)
edges = Join[edges, Table[{i, Mod[i + 3, n]}, {i, 0, n - 1}]]; (* Chord edges *)
If[EvenQ[n],
edges = Join[edges, Table[{i, Mod[i + n/2, n]}, {i, 0, n/2 - 1}]]
];
Graph[edges, VertexLabels -> "Name"]
];
a[n_] := Length@Select[
Tuples[{1, 2, 3}, n],
And @@ (#[[#[[1]] + 1]] != #[[#[[2]] + 1]] & /@
EdgeList[Cn3Graph[n]] /. {x_, y_} :> {x, y})
] &;
(* Generate terms for n from 6 to 20 *)
Table[a[n], {n, 6, 20}]
# Illustrative brute-force check for small n using networkx
import networkx as nx
from itertools import product
def Cn_k_graph(n, k):
G = nx.cycle_graph(n)
for i in range(n):
G.add_edge(i, (i+k)%n)
if n % 2 == 0:
for i in range(n//2):
G.add_edge(i, i+n//2)
return G
def count_colorings(G, colors=3):
nodes = list(G.nodes())
count = 0
for coloring in product(range(colors), repeat=len(nodes)):
if all(coloring[u] != coloring[v] for u,v in G.edges()):
count += 1
return count
# Example usage:
for n in range(6, 21):
G = Cn_k_graph(n, 3)
print(f'n={n}, colorings={count_colorings(G)}')
Comments