cp's OEIS Frontend

A223887 Number of 4-colored labeled graphs on n vertices.

%I A223887 #25 May 12 2025 06:46:08
%S A223887 1,4,28,340,7108,254404,15531268,1613235460,284556079108,
%T A223887 85107970698244,43112647751430148,36955277740855136260,
%U A223887 53562598422461559373828,131186989945696839128432644,542676256323680030599454982148
%N A223887 Number of 4-colored labeled graphs on n vertices.
%C A223887 A simple graph G is a k-colorable graph if it is possible to assign one of k' <= k colors to each vertex of G so that no two adjacent vertices receive the same color. Such an assignment of colors is called a coloring function for the graph.
%C A223887 A k-colored graph is a k-colorable graph together with its coloring function. This sequence gives the number of labeled 4-colored graphs on n vertices. An example is given below.
%C A223887 See A047863 for labeled 2-colored graphs on n vertices and A191371 for labeled 3-colored graphs on n vertices. See A076316 for labeled 4-colorable graphs on n vertices and A224068 for the count of labeled graphs colored using exactly 4 colors.
%D A223887 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973.
%H A223887 Andrew Howroyd, <a href="/A223887/b223887.txt">Table of n, a(n) for n = 0..50</a>
%H A223887 Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Bipartite, k-colorable and k-colored graphs</a>
%H A223887 Steven R. Finch, <a href="/A191371/a191371.pdf">Bipartite, k-colorable and k-colored graphs</a>, June 5, 2003. [Cached copy, with permission of the author]
%H A223887 R. C. Read, <a href="https://doi.org/10.4153/CJM-1960-035-0">The number of k-colored graphs on labelled nodes</a>, Canad. J. Math., 12 (1960), 410-414.
%H A223887 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/18.pdf">Acyclic orientation of graphs</a>, Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
%H A223887 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/k-ColorableGraph.html">k-Colorable Graph</a>
%F A223887 a(n) = sum {k = 0..n} binomial(n,k)*2^(k*(n-k))*b(k)*b(n-k), where b(n) := sum {k = 0..n} binomial(n,k)*2^(k*(n-k)).
%F A223887 Let E(x) = sum {n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is E(x)^4 = sum {n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + 4*x + 28*x^2/(2!*2) + 340*x^3/(3!*2^3) + .... In general, for k = 1, 2, ..., E(x)^k is a generating function for labeled k-colored graphs (see Stanley).
%e A223887 a(2) = 28: There are two labeled 4-colorable graphs on 2 nodes, namely
%e A223887 A)  1    2  B)  1    2
%e A223887     o    o      o----o
%e A223887 Using 4 colors there are 16 ways to color the graph of type A and 4*3 = 12 ways to color the graph of type B so that adjacent vertices do not share the same color. Thus there are in total 28 labeled 4-colored graphs on 2 vertices.
%o A223887 (PARI)
%o A223887 N=66;  x='x+O('x^N);
%o A223887 E=sum(n=0, N, x^n/(n!*2^binomial(n,2)) );
%o A223887 tgf=E^4;  v=concat(Vec(tgf));
%o A223887 v=vector(#v, n, v[n] * (n-1)! * 2^((n-1)*(n-2)/2) )
%o A223887 /* _Joerg Arndt_, Apr 10 2013 */
%Y A223887 Column k=4 of A322280.
%Y A223887 Equals 4 * A000686, A047863 (labeled 2-colored graphs), A076316, A191371 (labeled 3-colored graphs), A224068.
%K A223887 nonn,easy
%O A223887 0,2
%A A223887 _Peter Bala_, Apr 10 2013