A simpler characterization of a spectral lower bound on the clique number

DOI10.1007/S00186-009-0295-4MaRDI QIDQ966428zbMATH OpenOpenAlexFDO

Authors E. Alper Yildirim

Publication date 23 April 2010

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00186-009-0295-4

zbMATH Keywords

quadratic programmingadjacency matrixlower boundclique numberspectral decompositioncomputational resultsspectral lower bounds

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Spectral bounds for the clique and independence numbers of graphs
• New analytical lower bounds on the clique number of a graph
• More spectral bounds on the clique and independence numbers
• A generalization for the clique and independence numbers
• Lower bounds for the clique and the chromatic numbers of a graph

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Eigenvalue bounds for independent sets
• Evolution towards the maximum clique
• Exact bounds on the order of the maximum clique of a graph.
• Geometric algorithms and combinatorial optimization
• Laplacian spectral bounds for clique and independence numbers of graphs
• Maxima for Graphs and a New Proof of a Theorem of Turán
• More spectral bounds on the clique and independence numbers
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• Spectral bounds for the clique and independence numbers of graphs
• The smallest eigenvalue of \(K_{r}\)-free graphs

Cited in

(3)

• Sum-of-squares Lower Bounds for Planted Clique
• A new proof of the Fisher-Ryan bounds for the number of cliques of a graph
• New analytical lower bounds on the clique number of a graph

This page was built for publication: A simpler characterization of a spectral lower bound on the clique number

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