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
KEYWORD
nonn,hard,more
AUTHOR
Charles R Greathouse IV, Feb 01 2018
STATUS
approved