|
%I #26 Jun 03 2023 12:02:10
%S 1,2,5,11,22
%N Minimal number of vertices in a triangle-free graph with chromatic number n.
%C Mycielski's construction proves that this sequence is infinite.
%C 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.
%C Goedgebeur proves that 32 <= a(6) <= 40. - _Charles R Greathouse IV_, Mar 06 2018
%D F. Harary, Graph Theory, Addison-Wesley, Reading, Mass. (1969), p. 149.
%H V. Chvátal, <a href="https://doi.org/10.1007/BFb0066446">The minimality of the Mycielski graph</a>, 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.
%H Jan Goedgebeur, <a href="https://arxiv.org/abs/1707.07581">On minimal triangle-free 6-chromatic graphs</a> (2017)
%H House of Graphs, <a href="https://houseofgraphs.org/meta-directory/triangle-free-k-chromatic">Triangle-free k-chromatic graphs</a>
%H T. Jensen and G. F. Royle, <a href="https://doi.org/10.1002/jgt.3190190111">Small graphs with chromatic number 5</a>, A computer search, Journal of Graph Theory 19 (1995), pp. 107-116.
%H J. Mycielski, <a href="https://eudml.org/doc/210000">Sur le coloriage des graphes</a>, Colloq. Math. 3 (1955), pp. 161-162.
%H Gordon Royle, <a href="https://mathoverflow.net/a/292255/6043">Smallest triangle-free graph with chromatic number 5</a> (2018)
%F 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.
%e The unique graph for a(1) = 1 is a lone vertex.
%e The unique graph for a(2) = 2 is two vertices connected by an edge.
%e The unique graph for a(3) = 5 is the cycle graph C_5 (the pentagon).
%e The unique graph for a(4) = 11 is the Grötzsch graph.
%e There are 80 graphs for a(5) = 22, see Jensen & Royle reference and the Royle link.
%Y Cf. A006785, A024607.
%K nonn,hard,more
%O 1,2
%A _Charles R Greathouse IV_, Feb 01 2018
| 