Abstract It was shown that a uniquely vertex k-colorable graph of order n has minimum size n（k - 1） - （^k2）, and a uniquely vertex 3-colorable extremal graph with the minimum degree 3 can be constructed. In this n...Abstract It was shown that a uniquely vertex k-colorable graph of order n has minimum size n（k - 1） - （^k2）, and a uniquely vertex 3-colorable extremal graph with the minimum degree 3 can be constructed. In this note, we construct-an infinite familyof uniquely vertex k-colorable graphs of the order n, the size n（k - 1） - （^k2） and the minimum degree k by using a recursion method.展开更多
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...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 quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.展开更多
基金Project supported by the National Natural Science Foundation of China （Grant No.10101010）, and the Natural Science Development Foundation of Shanghai Municipal Commission of Education （Grant No.05AZ04）
文摘Abstract It was shown that a uniquely vertex k-colorable graph of order n has minimum size n（k - 1） - （^k2）, and a uniquely vertex 3-colorable extremal graph with the minimum degree 3 can be constructed. In this note, we construct-an infinite familyof uniquely vertex k-colorable graphs of the order n, the size n（k - 1） - （^k2） and the minimum degree k by using a recursion method.
文摘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 quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.
