|
|
A292528
|
|
Minimal number of vertices in a triangle-free 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.
|
|
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.
|
|
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
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|