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

DOI10.1016/J.LAA.2015.09.043zbMATH Open1326.05089OpenAlexW1841503951MaRDI QIDQ896848FDOQ896848

Authors Renata Sotirov, Edwin R. Van Dam 

Publication date 14 December 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.06595

zbMATH Keywords

semidefinite programmingchromatic numberstrongly regular graphsLaplacian eigenvaluesHamming graphsassociation schemes\(\max\)-\(k\)-cutwalk-regular graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Association schemes, strongly regular graphs (05E30) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• A class of spectral bounds for max \(k\)-cut
• scientific article; zbMATH DE number 4193718
• MAX k‐CUT and approximating the chromatic number of random graphs
• A lower bound for the chromatic number of a graph
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function

Cites Work

• scientific article; zbMATH DE number 17641 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1182569 (Why is no real title available?)
• scientific article; zbMATH DE number 2086928 (Why is no real title available?)
• scientific article; zbMATH DE number 4193718 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
• A comparison of the Delsarte and Lovász bounds
• A course in combinatorics.
• A remark on max-cut problem with an application to digital-analogue convertors
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An efficient semidefinite programming relaxation for the graph partition problem
• Bipartite Subgraphs and the Smallest Eigenvalue
• Clique-Web Facets for Multicut Polytopes
• Exploiting special structure in semidefinite programming: a survey of theory and applications
• Facets of the \(k\)-partition polytope
• Fast approximation algorithms on maxcut, k-coloring, and k-color ordering for VLSI applications
• Feasibility conditions for the existence of walk-regular graphs
• Geometry of cuts and metrics
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Laplacian eigenvalues and the maximum cut problem
• Lower Bounds for the Partitioning of Graphs
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• On semidefinite programming relaxations of maximum \(k\)-section
• On the cut polytope
• Polynomially Complete Fault Detection Problems
• Problems in algebraic combinatorics
• Realignment in the National Football League: Did they do it right?
• Semidefinite programming and eigenvalue bounds for the graph partition problem
• Semidefinite programs and association schemes
• Semidefinite relaxations for partitioning, assignment and ordering problems
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Solving \(k\)-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method
• Solving the max-cut problem using eigenvalues
• Symmetry groups, semidefinite programs, and sums of squares
• Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• The partition problem
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs

Cited In (14)

• The Maximum k-Colorable Subgraph Problem and Related Problems
• Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
• On the eigenvalues of Grassmann graphs, bilinear forms graphs and Hermitian forms graphs
• Max \(k\)-cut and the smallest eigenvalue
• Hamming graphs and special LCD codes
• Eigenvalues of Cayley graphs
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• A class of spectral bounds for max \(k\)-cut
• Projection results for the \(k\)-partition problem
• On graphs with eigenvectors in \(\{-1,0,1\}\) and the max \(k\)-cut problem
• Computational study of valid inequalities for the maximum \(k\)-cut problem
• A lower bound for the chromatic number of a graph
• New eigenvalue bound for the fractional chromatic number
• Max-cut and extendability of matchings in distance-regular graphs

Uses Software

• Biq Mac

This page was built for publication: New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896848)