Exact bounds on the order of the maximum clique of a graph.

DOI10.1016/S0166-218X(02)00386-4zbMath1051.68112MaRDI QIDQ1811073

Marco Budinich

Publication date: 10 June 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

GraphMaximum cliqueBound

Mathematics Subject Classification ID

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

Related Items (19)

Annealed replication: A new heuristic for the maximum clique problem ⋮ Maximum cliques of hypergraphs and polynomial optimization ⋮ A spinorial formulation of the maximum clique problem of a graph ⋮ A Motzkin-Straus type result for 3-uniform hypergraphs ⋮ Unnamed Item ⋮ On Motzkin-Straus type results for non-uniform hypergraphs ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ On graph-Lagrangians of hypergraphs containing dense subgraphs ⋮ On the largest graph-Lagrangian of 3-graphs with fixed number of edges ⋮ A convex relaxation bound for subgraph isomorphism ⋮ On Lagrangians of \(r\)-uniform hypergraphs ⋮ A continuous characterization of the maximum vertex-weighted clique in hypergraphs ⋮ A simpler characterization of a spectral lower bound on the clique number ⋮ Some Motzkin-Straus type results for non-uniform hypergraphs ⋮ Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ A generalization of the Motzkin-Straus theorem to hypergraphs ⋮ On the maxima of Motzkin-Straus programs and cliques of graphs ⋮ New analytical lower bounds on the clique number of a graph

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounds for the maximal characteristic root of a non-negative irreducible matrix
• Lower bounds for the clique and the chromatic numbers of a graph
• Spectral bounds for the clique and independence numbers of graphs
• A bound on the spectral radius of graphs
• The maximum clique problem
• The sandwich theorem
• Evolution towards the maximum clique
• Matrix Analysis
• A global optimization approach for solving the maximum clique problem
• Continuous Characterizations of the Maximum Clique Problem
• Maxima for Graphs and a New Proof of a Theorem of Turán
• The Eigenvalues of a Graph and Its Chromatic Number
• Upper Bounds on the Order of a Clique of a Graph

This page was built for publication: Exact bounds on the order of the maximum clique of a graph.