A383733 Number of proper 3-colorings of the generalized chorded cycle graph C_n^{(3)}.
42, 0, 0, 18, 186, 66, 0, 234, 930, 750, 0, 2244, 4578, 6498, 120
Offset: 6
Examples
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.
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
- G. D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. Math., 14:42-46.
- Ronald C. Read, An Introduction to Chromatic Polynomials, Journal of Combinatorial Theory, 4(1968),52-71.
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.
Programs
-
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}] -
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)}')
Comments