login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A292528 Minimal number of vertices in a triangle-free graph with chromatic number n. 0
1, 2, 5, 11, 22 (list; graph; refs; listen; history; text; internal format)
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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 20:36 EDT 2020. Contains 337374 sequences. (Running on oeis4.)