

A122695


Number of edges in the nth Mycielski graph. This sequence of graphs is formed, starting from the empty graph, by repeatedly applying a construction of Mycielski for generating trianglefree graphs with arbitrarily large chromatic number.


1



0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, 203600, 613871, 1847756, 5555555, 16691240, 50122871, 150466916, 451597355, 1355185280, 4066342271, 12200599676, 36604944755, 109821125720, 329475960071, 988453046036, 2965409469755, 8896329072560
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

The number of vertices in the Mycielski graphs is given by sequence A083329.


LINKS

Colin Barker, Table of n, a(n) for n = 0..1000
J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3: 161162, 1955.
Eric Weisstein's World of Mathematics, Mycielski Graph
Index entries for linear recurrences with constant coefficients, signature (6,11,6).


FORMULA

a(n) = 3*a(n1) + 3*2^(n2)  1.
From Colin Barker, Mar 07 2012 and Jan 16 2016: (Start)
a(n) = (1827*2^n+14*3^n)/36 for n>1.
a(n) = 6*a(n1)11*a(n2)+6*a(n3) for n>4.
G.f.: x^2*(1x+x^2) / ((1x)*(12*x)*(13*x)).
(End)


EXAMPLE

The first few graphs in the sequence of Mycielski graphs are the null graph, K1, K2, C5 and the Graezsch graph with 11 vertices and 20 edges. Thus the first entries in this sequence are 0, 0, 1, 5 and 20.


PROG

(PARI) concat(vector(2), Vec(x^2*(1x+x^2)/((1x)*(12*x)*(13*x)) + O(x^40))) \\ Colin Barker, Jan 16 2016


CROSSREFS

Cf. A083329.
Sequence in context: A036683 A054444 A121332 * A269914 A066822 A137212
Adjacent sequences: A122692 A122693 A122694 * A122696 A122697 A122698


KEYWORD

easy,nonn


AUTHOR

David Eppstein, Oct 29 2006


STATUS

approved



