

A292528


Minimal number of vertices in a trianglefree graph with chromatic number n.


0




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, AddisonWesley, 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. 243246. Lecture Notes in Mathematics 406, Springer, Berlin, 1974.
Jan Goedgebeur, On minimal trianglefree 6chromatic graphs (2017)
House of Graphs, Trianglefree kchromatic graphs
T. Jensen and G. F. Royle, Small graphs with chromatic number 5, A computer search, Journal of Graph Theory 19 (1995), pp. 107116.
J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955), pp. 161162.
Gordon Royle, Smallest trianglefree graph with chromatic number 5 (2018)


FORMULA

For n > 3, the Mycielskian of a graph for a(n1) shows that a(n) <= 2*a(n1) + 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: A000785 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



