A292528 Minimal number of vertices in a triangle-free graph with chromatic number n.

1, 2, 5, 11, 22

Offset: 1

Author

Charles R Greathouse IV, Feb 01 2018

Keywords

• nonn
• hard
• more

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

Examples

			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.
		

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)

Crossrefs

Cf. A006785, A024607.

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.