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

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

Table of n, a(n) for n=1..5.

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

Cf. A006785, A024607.

Sequence in context: A364591 A049936 A058358 * A135119 A290778 A291590

Adjacent sequences: A292525 A292526 A292527 * A292529 A292530 A292531

Keyword

nonn,hard,more

Author

Charles R Greathouse IV, Feb 01 2018

Status

approved