Algorithms for finding in the lump both bounds of the chromatic number of a graph
Open Access
- 1 January 1976
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 19 (4) , 329-332
- https://doi.org/10.1093/comjnl/19.4.329
Abstract
Many problems of scheduling or timetabling are reduced to finding the chromatic number of a graph, i.e. the minimum number of colours assigned to vertices so that no two adjacent vertices have the same colour. In this paper algorithms for finding in the lump a lower bound and an upper bound of the chromatic number are given. The results obtained for several graphs by the computer are indicated and compared with other methods.Keywords
This publication has 0 references indexed in Scilit: