In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic 0-1 programming and its relaxed rpoblem, k-coloring problem is converted into a class of (continuous) nonconvex quadratic programs, and several theoretic results are also introduced. Thirdly, linear programming approximate algorithm is quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed and sufficient computation experiments are reported.
展开▼
