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

DOI10.1016/S0166-218X(02)00386-4MaRDI QIDQ1811073zbMATH OpenFDO

Authors 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

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

Recommendations

• New analytical lower bounds on the clique number of a graph
• Lower bounds for the clique and the chromatic numbers of a graph
• Spectral bounds for the clique and independence numbers of graphs
• The maximum clique and the signless Laplacian eigenvalues
• scientific article; zbMATH DE number 1560331

Cites work

• scientific article; zbMATH DE number 3745227 (Why is no real title available?)
• scientific article; zbMATH DE number 510844 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A bound on the spectral radius of graphs
• A global optimization approach for solving the maximum clique problem
• Bounds for the maximal characteristic root of a non-negative irreducible matrix
• Continuous Characterizations of the Maximum Clique Problem
• Evolution towards the maximum clique
• Lower bounds for the clique and the chromatic numbers of a graph
• Matrix Analysis
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Spectral bounds for the clique and independence numbers of graphs
• The Eigenvalues of a Graph and Its Chromatic Number
• The maximum clique problem
• The sandwich theorem
• Upper Bounds on the Order of a Clique of a Graph

Cited in

(21)

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

Describes a project that uses

Uses Software

• DIMACS

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

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