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

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)216 - 234
Number of pages18
JournalLinear Algebra and its Applications
Volume488
DOIs
Publication statusPublished - 1 Jan 2016

Fingerprint

Chromatic number
Eigenvalue Bounds
Graph in graph theory
Semidefinite Programming Relaxation
Regular Graph
Laplacian Eigenvalues
Strongly Regular Graph
Association Scheme
First Eigenvalue
Largest Eigenvalue
Walk
Closed-form
Optimal Solution

Keywords

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

Cite this

@article{7f8ebc0deccf4597902cc3ba73a0c81e,
title = "New bounds for the max-k-cut and chromatic number of a graph",
abstract = "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.",
keywords = "max-k-cut, chromatic number, semidefinite programming, Laplacian eigenvalues, walk-regular graphs, association schemes, strongly regular graphs, Hamming graphs",
author = "{van Dam}, Edwin and Renata Sotirov",
year = "2016",
month = "1",
day = "1",
doi = "10.1016/j.laa.2015.09.043",
language = "English",
volume = "488",
pages = "216 -- 234",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",

}

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

In: Linear Algebra and its Applications, Vol. 488, 01.01.2016, p. 216 - 234.

Research output: Contribution to journalArticleScientificpeer-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 -