login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

A122695
Number of edges in the n-th Mycielski graph.
2
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
OFFSET
0,4
COMMENTS
The Mycielski graphs are formed, starting from the empty graph, by repeatedly applying a construction of Mycielski for generating triangle-free graphs with arbitrarily large chromatic number.
The number of vertices in the Mycielski graphs is given by sequence A083329.
Also the number of maximal and maximum cliques in the n-Mycielski graph for n > 1. - Eric W. Weisstein, Dec 01 2017
LINKS
J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3: 161-162, 1955.
Eric Weisstein's World of Mathematics, Maximal Clique
Eric Weisstein's World of Mathematics, Maximum Clique
Eric Weisstein's World of Mathematics, Mycielski Graph
Emre Yolcu, Xinyu Wu, Marijn J. H. Heule, Mycielski graphs and PR proofs, Carnegie Mellon University (2020).
FORMULA
a(n) = 3*a(n-1) + 3*2^(n-3) - 1 for n > 2. [corrected by Moeez Muhammad, Apr 17 2021]
From Colin Barker, Mar 07 2012 and Jan 16 2016: (Start)
a(n) = (18-27*2^n+14*3^n)/36 for n>1.
a(n) = 6*a(n-1)-11*a(n-2)+6*a(n-3) for n>4.
G.f.: x^2*(1-x+x^2) / ((1-x)*(1-2*x)*(1-3*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.
MATHEMATICA
Table[If[n < 2, 0, (18 - 27 2^n + 14 3^n)/36], {n, 0, 10}] (* Eric W. Weisstein, Dec 01 2017 *)
Join[{0, 0}, LinearRecurrence[{6, -11, 6}, {1, 5, 20}, 20]] (* Eric W. Weisstein, Dec 01 2017 *)
ientList[Series[x^2 (1 - x + x^2)/(1 - 6 x + 11 x^2 - 6 x^3), {x, 0, 20}], x] (* Eric W. Weisstein, Dec 01 2017 *)
PROG
(PARI) concat(vector(2), Vec(x^2*(1-x+x^2)/((1-x)*(1-2*x)*(1-3*x)) + O(x^40))) \\ Colin Barker, Jan 16 2016
CROSSREFS
Cf. A083329.
Sequence in context: A036683 A054444 A121332 * A269914 A066822 A137212
KEYWORD
easy,nonn
AUTHOR
David Eppstein, Oct 29 2006
STATUS
approved