On some conjectures of Graffiti. (English) Zbl 0887.05017
The computer program Galatea Gabriella Graffiti [S. Fajtlowicz, University of Houston, 1996] made several conjectures concerning the chromatic numbers of graphs. The authors prove one of these conjectures, and disprove four.
Reviewer: C.Jagger (Cambridge)
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
Software:
GRAFFITIReferences:
| [1] | Bollobás, B., Random Graphs (1985), Academic Press: Academic Press London · Zbl 0567.05042 |
| [2] | B. Bollobás, O.M. Riordan, Colourings generated by monotone properties, Random Structures and Algorithms, submitted.; B. Bollobás, O.M. Riordan, Colourings generated by monotone properties, Random Structures and Algorithms, submitted. |
| [3] | Bollobás, B.; Sauer, N., Uniquely colourable graphs with large girth, Can. J. Math., 28, 1340-1344 (1976) · Zbl 0344.05115 |
| [4] | Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statist., 23, 493-507 (1952) · Zbl 0048.11804 |
| [5] | DeLaVina, E.; Fajtlowicz, S., Ramseyan Properties of graphs, Electronic J. Combin., 3, 1 (1996), Research Paper 26 · Zbl 0885.05087 |
| [6] | Descartes, B.; Tutte, W. T., A three colour problem, Solution (March 1948), Eureka, April 1947 |
| [7] | Erdös, P., Graph theory and probability, Can. J. Math., 11, 34-38 (1959) · Zbl 0084.39602 |
| [8] | Fajtlowicz, S., Written on the Wall, Conjectures made by the program Galatea Gabriella Graffiti (1996), University of Houston |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
