Problem 7.3: Smallest Triangle-Free k-Chromatic Graph
The problem of the order of magnitude of n(k) has
been solved by Kim in the paper [J.H. Kim, The Ramsey Number R(3,t) has Order
of Magnitude t2/log t, Manuscript 1994].
Some further details can be found in the paper
[J. Spencer, Modern Probabilistic Methods in Combinatorics,
Surveys in Combinatorics 1995, Cambridge University Press,
pp. 215-231].
The above result of J.H. Kim implies that n(k) has
order of magnitude k2 log k.
We do not know if the limit of n(k)/(k2 log k)
exists when k tends to infinity. The remaining subproblems
of Problem 7.3 are still open.
August 10, 1995 T.R. Jensen and B. Toft.
The paper [Y. Caro, On The Covering Number Of Combinatorial Structures,
Ars Combin. 29B (1990) 111-124] already contains, as
a special case, the
greedy coloring argument that we have presented as a proof that
k2 log k is a lower bound for the order of magnitude of n(k).
Our argument for the special case of triangle-free graphs may
also be found in [B. Toft, Graph Colouring Problems part I,
Odense University Preprint, April 1987].
The above paper of Y. Caro deals with a more general setting, in which also
a number of new results on the cochromatic number (see
Problem 17.3)
are obtained.
August 13, 1997 T.R. Jensen and B. Toft.
Last modified August 13, 1997 Tommy R. Jensen