A383733 - OEIS

%I #24 Nov 13 2025 10:34:23

%S 42,0,0,18,186,66,0,234,930,750,0,2244,4578,6498,120

%N Number of proper 3-colorings of the generalized chorded cycle graph C_n^{(3)}.

%C 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.

%C 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.

%C The observed modular non-monotone pattern is unique and does not match known classical graph families, motivating deeper combinational and algebraic investigations.

%C 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.

%C 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.

%C 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.

%D N. L. Biggs, Algebraic Graph Theory. Cambridge University Press, 2nd ed., 1993.

%D D. B. West, Introduction to Graph Theory. Prentice Hall, 2nd ed., 2001.

%D R. J. Wilson, Graph Theory. Longman, 5th impression, 1996.

%H George D. Birkhoff, <a href="https://www.jstor.org/stable/1967597">A determinant formula for the number of ways of coloring a map</a>, Ann. Math., 14:42-46.

%H Rogelio N. Lopez-Bonilla, Julian Allagan, Shawn M. Langley, and Angel J. Clinton, <a href="https://arxiv.org/abs/2509.05845">Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs</a>, arXiv:2509.05845 [math.CO], 2025. See pp. 1, 8, 11.

%H Ronald C. Read, <a href="https://doi.org/10.1016/S0021-9800(68)80087-0">An Introduction to Chromatic Polynomials</a>, Journal of Combinatorial Theory, 4(1968), 52-71.

%H Rogelio Lopez-Bonilla, Julian Allagan, Shawn M. Langley, and Angel J. Clinton, <a href="https://doi.org/10.9734/jamcs/2025/v40i102060">Chromatic Polynomials of C_n^(3) Graphs: Lucas Sequences, phi^n Asymptotics and Linear Recurrence Existence</a>, J. Adv. Math. Comp. Sci. (2025) Vol. 40, Issue 10, Art. JAMCS.146917, 79-98. <a href="https://www.researchgate.net/profile/Rogelio-Lopez-Bonilla/publication/397141446_Chromatic_Polynomials_of_C_Graphs_Lucas_Sequences_ph_Asymptotics_and_Linear_Recurrence_Existence">Alternative link</a>. See pp. 80, 95.

%e For n=6, consider the graph C_6^(3), constructed as follows:

%e - Start with a cycle graph (hexagon) having vertices labeled {0,1,2,3,4,5}.

%e - Add chords connecting vertex i with vertex i+3 mod 6, forming edges (0,3), (1,4), (2,5).

%e - 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.)

%e 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).

%e Thus, a(6)=42.

%p with(GraphTheory):

%p Cn3_graph := proc(n)

%p local G, i;

%p G := CycleGraph(n);

%p for i from 0 to n-1 do

%p     AddEdge(G, {i, (i+3) mod n});

%p end do;

%p if modp(n, 2) = 0 then

%p     for i from 0 to n/2 - 1 do

%p         AddEdge(G, {i, (i + n/2) mod n});

%p     end do;

%p end if;

%p return G;

%p end proc:

%p a := proc(n) local G;

%p G := Cn3_graph(n);

%p return ChromaticPolynomial(G, 3);

%p end proc:

%p # Compute initial terms from n=6 to n=20:

%p seq(a(n), n=6..20);

%t Cn3Graph[n_] := Module[{g, edges, i},

%t   edges = Table[{i, Mod[i + 1, n]}, {i, 0, n - 1}]; (* Cycle edges *)

%t   edges = Join[edges, Table[{i, Mod[i + 3, n]}, {i, 0, n - 1}]]; (* Chord edges *)

%t   If[EvenQ[n],

%t    edges = Join[edges, Table[{i, Mod[i + n/2, n]}, {i, 0, n/2 - 1}]]

%t   ];

%t   Graph[edges, VertexLabels -> "Name"]

%t ];

%t a[n_] := Length@Select[

%t   Tuples[{1, 2, 3}, n],

%t   And @@ (#[[#[[1]] + 1]] != #[[#[[2]] + 1]] & /@

%t     EdgeList[Cn3Graph[n]] /. {x_, y_} :> {x, y})

%t ] &;

%t (* Generate terms for n from 6 to 20 *)

%t Table[a[n], {n, 6, 20}]

%o (Python)

%o # Illustrative brute-force check for small n using networkx

%o import networkx as nx

%o from itertools import product

%o def Cn_k_graph(n, k):

%o     G = nx.cycle_graph(n)

%o     for i in range(n):

%o         G.add_edge(i, (i+k)%n)

%o     if n % 2 == 0:

%o         for i in range(n//2):

%o             G.add_edge(i, i+n//2)

%o     return G

%o def count_colorings(G, colors=3):

%o     nodes = list(G.nodes())

%o     count = 0

%o     for coloring in product(range(colors), repeat=len(nodes)):

%o         if all(coloring[u] != coloring[v] for u,v in G.edges()):

%o             count += 1

%o     return count

%o # Example usage:

%o for n in range(6, 21):

%o     G = Cn_k_graph(n, 3)

%o     print(f'n={n}, colorings={count_colorings(G)}')

%Y 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).

%Y 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.

%K nonn,hard,more

%O 6,1

%A _Rogelio Lopez Bonilla_, May 07 2025