login
A292528
Minimal number of vertices in a triangle-free graph with chromatic number n.
0
1, 2, 5, 11, 22
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.
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.
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
Sequence in context: A364591 A049936 A058358 * A135119 A290778 A291590
KEYWORD
nonn,hard,more
AUTHOR
STATUS
approved