کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4598824 | 1631107 | 2016 | 19 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: New bounds for the max-k-cut and chromatic number of a graph New bounds for the max-k-cut and chromatic number of a graph](/preview/png/4598824.png)
We consider several semidefinite programming relaxations for the max-k-cut problem, with increasing complexity. The optimal solution of the weakest presented semidefinite programming relaxation has a closed form expression that includes the largest Laplacian eigenvalue of the graph under consideration. This is the first known eigenvalue bound for the max-k -cut when k>2k>2 that is applicable to any graph. This bound is exploited to derive a new eigenvalue bound on the chromatic number of a graph. For regular graphs, the new bound on the chromatic number is the same as the well-known Hoffman bound; however, the two bounds are incomparable in general.We prove that the eigenvalue bound for the max-k-cut is tight for several classes of graphs. We investigate the presented bounds for specific classes of graphs, such as walk-regular graphs, strongly regular graphs, and graphs from the Hamming association scheme.
Journal: Linear Algebra and its Applications - Volume 488, 1 January 2016, Pages 216–234