A159233 Number of edge colorings of the Petersen graph.

0, 0, 0, 0, 49920, 18936480, 1293857280, 34839270480, 518880929280, 5122755187200, 37376074229760, 216261381584160, 1041571537839360, 4323020652281760, 15864787390932480, 52496402135289840, 159036030441200640, 446469968164496640, 1172916400659517440

Offset: 0

Author

Alois P. Heinz, Apr 06 2009

Keywords

• nonn
• easy

Comments

The Petersen graph G is a cubic symmetric graph on 10 vertices and 15 edges with edge chromatic number 4. a(n) is also the number of (vertex) n-colorings of L(G), the line graph (or interchange graph) of G.

"An edge coloring of a graph G is a coloring of the edges of G such that adjacent edges (or the edges bounding different regions) receive different colors. An edge coloring containing the smallest possible number of colors for a given graph is known as a minimum edge coloring." - Eric Weisstein, Edge Coloring.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Timme, Marc; van Bussel, Frank; Fliegner, Denny; Stolzenberg, Sebastian (2009) "Counting complex disordered states by efficient pattern matching: chromatic polynomials and Potts partition functions", New J. Phys. 11 023001, doi: 10.1088/1367-2630/11/2/023001.
• Eric Weisstein's World of Mathematics, Petersen Graph
• Eric Weisstein's World of Mathematics, Edge Coloring
• Wikipedia, Edge Coloring
• Index entries for linear recurrences with constant coefficients, signature (16, -120, 560, -1820, 4368, -8008, 11440, -12870, 11440, -8008, 4368, -1820, 560, -120, 16, -1).

Crossrefs

Cf. A270842 for edge colorings under the automorphisms of the Petersen graph. A296913.

Programs

Maple

a:= n-> n^15 -30*n^14 +425*n^13 -3780*n^12 +23658*n^11 -110594*n^10 +399500*n^9 -1136005*n^8 +2560246*n^7 -4553907*n^6 +6285354*n^5 -6504300*n^4 +4739880*n^3 -2156064*n^2 +455616*n: seq(a(n), n=0..20);

Mathematica

Table[n^15 - 30 n^14 + 425 n^13 - 3780 n^12 + 23658 n^11 - 110594 n^10 + 399500 n^9 - 1136005 n^8 + 2560246 n^7 - 4553907 n^6 + 6285354 n^5 - 6504300 n^4 + 4739880 n^3 - 2156064 n^2 + 455616 n, {n, 0, 18}] (* Michael De Vlieger, Mar 27 2016 *)

PARI

a(n)=prod(i=0,3,n-i)*(n^11 -24*n^10 +270*n^9 -1890*n^8 +9204*n^7 -32960*n^6 +89156*n^5 -183285*n^4 +282060*n^3 -310476*n^2 +220128*n -75936) \\ Charles R Greathouse IV, Nov 28 2012

Formula

a(n) = n^15 -30*n^14 + ... (see Maple program).

G.f.: 240 * x^4 * (120539*x^11 +4939568*x^10 [phone]*x^9 [phone]*x^8 [phone]*x^7 [phone]*x^6 [phone]*x^5 [phone]*x^4 [phone]*x^3 +4153600*x^2 +75574*x +208) / (x-1)^16. - Colin Barker, Nov 28 2012