login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A223887 Number of 4-colored labeled graphs on n vertices. 9
1, 4, 28, 340, 7108, 254404, 15531268, 1613235460, 284556079108, 85107970698244, 43112647751430148, 36955277740855136260, 53562598422461559373828, 131186989945696839128432644, 542676256323680030599454982148 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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.

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.

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.

REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..50

S. R. Finch, Bipartite, k-colorable and k-colored graphs

S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]

R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410—414.

R. P. Stanley, Acyclic orientation of graphs Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.

Eric Weisstein's World of Mathematics, k-Colorable Graph

FORMULA

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

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

EXAMPLE

a(2) = 28: There are two labeled 4-colorable graphs on 2 nodes, namely

A)  1    2  B)  1    2

    o    o      o----o

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.

PROG

(PARI)

N=66;  x='x+O('x^N);

E=sum(n=0, N, x^n/(n!*2^binomial(n, 2)) );

tgf=E^4;  v=concat(Vec(tgf));

v=vector(#v, n, v[n] * (n-1)! * 2^((n-1)*(n-2)/2) )

/* Joerg Arndt, Apr 10 2013 */

CROSSREFS

Column k=4 of A322280.

Equals 4 * A000686, A047863 (labeled 2-colored graphs), A076316, A191371 (labeled 3-colored graphs), A224068.

Sequence in context: A113371 A280570 A080636 * A140425 A193198 A165193

Adjacent sequences:  A223884 A223885 A223886 * A223888 A223889 A223890

KEYWORD

nonn,easy

AUTHOR

Peter Bala, Apr 10 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 25 03:49 EST 2020. Contains 331241 sequences. (Running on oeis4.)