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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A292528 Minimal number of vertices in a triangle-free graph with chromatic number n. 0
 1, 2, 5, 11, 22 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Mycielski's construction proves that this sequence is infinite. Harary states in an exercise (12.19) that a(4) <= 11. Chvátal proves that a(4) = 11 and gives a proof of uniqueness. Jensen & Royle prove that a(5) = 22. Goedgebeur proves that 32 <= a(6) <= 40. - Charles R Greathouse IV, Mar 06 2018 REFERENCES F. Harary, Graph Theory, Addison-Wesley, Reading, Mass. (1969), p. 149. LINKS V. Chvátal, The minimality of the Mycielski graph, Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Ed. by R. A. Bari and F. Harary, pp. 243-246. Lecture Notes in Mathematics 406, Springer, Berlin, 1974. Jan Goedgebeur, On minimal triangle-free 6-chromatic graphs (2017) House of Graphs, Triangle-free k-chromatic graphs T. Jensen and G. F. Royle, Small graphs with chromatic number 5, A computer search, Journal of Graph Theory 19 (1995), pp. 107-116. J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955), pp. 161-162. Gordon Royle, Smallest triangle-free graph with chromatic number 5 (2018) FORMULA For n > 3, the Mycielskian of a graph for a(n-1) shows that a(n) <= 2*a(n-1) + 1. This can be used to show that a(n) <= 3/4 * 2^n - 1 for n > 1. EXAMPLE The unique graph for a(1) = 1 is a lone vertex. The unique graph for a(2) = 2 is two vertices connected by an edge. The unique graph for a(3) = 5 is the cycle graph C_5 (the pentagon). The unique graph for a(4) = 11 is the Grötzsch graph. There are 80 graphs for a(5) = 22, see Jensen & Royle reference and the Royle link. CROSSREFS Cf. A006785, A024607. Sequence in context: A000785 A049936 A058358 * A135119 A290778 A291590 Adjacent sequences:  A292525 A292526 A292527 * A292529 A292530 A292531 KEYWORD nonn,hard,more AUTHOR Charles R Greathouse IV, Feb 01 2018 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.

Last modified September 26 20:36 EDT 2020. Contains 337374 sequences. (Running on oeis4.)