### Abstract

Original language | English |
---|---|

Pages (from-to) | 216 - 234 |

Number of pages | 18 |

Journal | Linear Algebra and its Applications |

Volume | 488 |

DOIs | |

Publication status | Published - 1 Jan 2016 |

### Fingerprint

### Keywords

- max-k-cut
- chromatic number
- semidefinite programming
- Laplacian eigenvalues
- walk-regular graphs
- association schemes
- strongly regular graphs
- Hamming graphs

### Cite this

}

**New bounds for the max-k-cut and chromatic number of a graph.** / van Dam, Edwin; Sotirov, Renata.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - New bounds for the max-k-cut and chromatic number of a graph

AU - van Dam, Edwin

AU - Sotirov, Renata

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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>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.

AB - 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>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.

KW - max-k-cut

KW - chromatic number

KW - semidefinite programming

KW - Laplacian eigenvalues

KW - walk-regular graphs

KW - association schemes

KW - strongly regular graphs

KW - Hamming graphs

U2 - 10.1016/j.laa.2015.09.043

DO - 10.1016/j.laa.2015.09.043

M3 - Article

VL - 488

SP - 216

EP - 234

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -