On the chromatic properties of graphs up to 10 vertices. (English) Zbl 0648.05021

Read, Ronald C.

Combinatorics, graph theory and computing, Proc. 18th Southeast. Conf., Boca Raton/Fl. 1987, Congr. Numerantium 59, 243-255 (1987).

[For the entire collection see Zbl 0638.00009.]
The paper presents results on the chromatic properties of graphs up to 10 vertices. The investigations are based on a catalogue of all graphs on 10 vertices (see: R. E. Cameron, C. J. Colbourn, R. C. Read and N. C. Wormald [J. Graph Theory 9, 551-562 (1985)]). The computation of the chromatic polynomials of graphs in question can be used for recognizing other properties of the graph. For graphs on up to nine vertices the questions
– How many distinct chromatic polynomials are there?
– How many uniquely colourable graphs are there?
– How many graphs with given chromatic number are there?
are answered.
The author hopes to find similar results for graphs on ten vertices using the CRAY 22 computer at the University of Toronto. Note that the problem of computing chromatic polynomials is known to be NP-complete.

Reviewer: U.Baumann

MSC:

05C15	Coloring of graphs and hypergraphs
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics

Keywords:

chromatic properties; graphs up to 10 vertices; computation; chromatic polynomials