OFFSET
6,1
COMMENTS
The sequence counts the exact number of proper vertex colorings using 3 colors of circular chord graphs C_n^(3), defined as cycle graphs C_n with chords connecting vertices at offset 3 (vertices i and i+3 mod n), and with diametric edges added for even n.
Notably, the sequence displays modular phase transitions and recurring zeros for even values of n divisible by 4 (n=8,12,16,...). These zeros occur due to structural constraints from chords and diametric edges preventing any valid 3-colorings.
The observed modular non-monotone pattern is unique and does not match known classical graph families, motivating deeper combinational and algebraic investigations.
Empirical analysis using the transfer matrix method indicates that the sequence a(n) = P(C_n^(3), 3) satisfies a linear recurrence relation of finite order. Specifically, the number of 3-colorings of C_n^(3) can be represented using adjacency-like matrices encoding local constraints imposed by chords and diametric edges.
Formally, let T be the transfer matrix representing transitions of valid colorings between successive vertices or segments of the graph. The count a(n) corresponds to a trace or specific linear combination of powers of T: a(n) = Tr(M * T^n), for some suitable projection matrix M, capturing the graph's cyclical boundary conditions and additional chord and diameter constraints.
The minimal polynomial of the transfer matrix T dictates the order of this recurrence. Although computationally validated for initial terms, determining an explicit closed-form solution or exact minimal polynomial and recurrence relation analytically remains an open combinational and algebraic problem.
REFERENCES
N. L. Biggs, Algebraic Graph Theory. Cambridge University Press, 2nd ed., 1993.
D. B. West, Introduction to Graph Theory. Prentice Hall, 2nd ed., 2001.
R. J. Wilson, Graph Theory. Longman, 5th impression, 1996.
LINKS
George D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. Math., 14:42-46.
Rogelio N. Lopez-Bonilla, Julian Allagan, Shawn M. Langley, and Angel J. Clinton, Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs, arXiv:2509.05845 [math.CO], 2025. See pp. 1, 8, 11.
Ronald C. Read, An Introduction to Chromatic Polynomials, Journal of Combinatorial Theory, 4(1968), 52-71.
Rogelio Lopez-Bonilla, Julian Allagan, Shawn M. Langley, and Angel J. Clinton, Chromatic Polynomials of C_n^(3) Graphs: Lucas Sequences, phi^n Asymptotics and Linear Recurrence Existence, J. Adv. Math. Comp. Sci. (2025) Vol. 40, Issue 10, Art. JAMCS.146917, 79-98. Alternative link. See pp. 80, 95.
EXAMPLE
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.
MAPLE
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);
MATHEMATICA
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}]
PROG
(Python)
# 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)}')
CROSSREFS
Cf. A000670 (number of preferential arrangements), A001047 (chromatic polynomial of cycles at x=3), A003049 (chromatic polynomial of complete graphs), A129912 (number of 3-colorings of certain circulant graphs).
Related to chromatic polynomial evaluations and modular coloring patterns not captured by standard families. May also be compared to sequences involving nonzero chromatic roots and Beraha numbers.
KEYWORD
nonn,hard,more
AUTHOR
Rogelio Lopez Bonilla, May 07 2025
STATUS
approved