A270842 -id:A270842 - cp's OEIS frontend

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

Alois P. Heinz, Apr 06 2009

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.

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

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

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);

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 *)

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

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

G.f.: 240 * x^4 * (120539*x^11 +4939568*x^10 +71258450*x^9 +441713760*x^8 +1285299570*x^7 +1834236432*x^6 +1296079344*x^5 +442507920*x^4 +68258235*x^3 +4153600*x^2 +75574*x +208) / (x-1)^16. - Colin Barker, Nov 28 2012

A270843 Number of nonisomorphic edge colorings of the Petersen graph with exactly n colors.

Original entry on oeis.org

1, 394, 122601, 8510140, 210940745, 2524556538, 17167621086, 72787256640, 202996629360, 382918536000, 492133561920, 424994169600, 236107872000, 76281004800, 10897286400

Offset: 1

Marko Riedel, Mar 24 2016

This is zero when n is more than fifteen because only fifteen edges are available.
These are not colorings in the strict sense, since there is no requirement that adjacent edges have different colors. - N. J. A. Sloane, Mar 28 2016
The value for n=15 is 15!/120 because all orbits are the same size namely 120 (order of the symmetric group on five elements) when each of the 15 edges has a unique color. - Marko Riedel, Mar 28 2016

Math StackExchange, Edge colorings of the Petersen graph

Cf. A270842, A063843.

Cycle index of the automorphisms acting on the edges is (1/120)*S[1]^15+(5/24)*S[2]^6*S[1]^3+(1/4)*S[4]^3*S[2]*S[1]+(1/6)*S[3]^5+(1/6)*S[3]*S[6]^2+(1/5)*S[5]^3.

Inclusion-exclusion yields a(n) = sum(C(n, q)*(-1)^q*A270842(n - q), q = 0 .. n)

cp's OEIS Frontend

A159233 Number of edge colorings of the Petersen graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula