On the chromatic number of graphs (Q5942344)

Computing the chromatic number of a graph is NP-hard---in fact, it is NP-hard to colour a graph with fewer than twice the minimum number of colours [\textit{M. R. Garey} and \textit{D. S. Johnson}, The complexity of near-optimal graph coloring, J. Assoc. Comput. Mach. 23, 43-49 (1976; Zbl 0322.05111)]. For large graphs, therefore, one must be content with an approximately minimal colouring. But to test an approximate colouring algorithm, one needs a wide variety of large graphs of known chromatic number. The first method of generating random graphs of known chromatic number appeared in [\textit{F. T. Leighton}, A graph coloring algorithm for large scheduling problems, J. Res. Natl. Bur. Stand. 84, 489-506 (1979; Zbl 0437.68021)]. ``In this paper, a new 0-1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program.'' Reviewer's remark: This reviewer would have liked to see a discussion of the advantages of the method presented in this paper over the one in [\textit{F. T. Leighton}, loc. cit.] and either a definition of the term KKT or a reference to such a definition.