Lower bounds for the clique and the chromatic numbers of a graph

DOI10.1016/0166-218X(83)90015-XzbMATH Open0535.05029MaRDI QIDQ790829FDOQ790829

Authors: C. H. Elphick, Christopher S. Edwards

Publication date: 1983

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

Recommendations

Lower bounds on the clique-chromatic numbers of some distance graphs
Bounds for the chromatic number of graphs with partial information
Bounds for the chromatic number of a graph
More spectral bounds on the clique and independence numbers
New bounds for the clique-chromatic numbers of Johnson graphs

spectral radius chromatic number clique number

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Cites Work

Title not available (Why is that?)
The Largest Vertex Degree Sum for a Triangle in a Graph
An upper bound for the chromatic number of a graph and its application to timetabling problems
Title not available (Why is that?)
Title not available (Why is that?)
Bounds for the chromatic number of a graph
A lower bound on the chromatic number of a graph
Title not available (Why is that?)
Continuous Timetabling Problems
Title not available (Why is that?)

Cited In (44)

Eigenvalues and triangles in graphs
The maximum clique problem
A Brualdi-Hoffman-Turán problem on cycles
Two conjectured strengthenings of Turán's theorem
A simpler characterization of a spectral lower bound on the clique number
Computers and discovery in algebraic graph theory
A refined Turán theorem
The signless Laplacian spectral radius of graphs with a prescribed number of edges
More spectral bounds on the clique and independence numbers
Turán's theorem implies Stanley's bound
A note on eigenvalues of signed graphs
Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
Conjectured bounds for the sum of squares of positive eigenvalues of a graph
New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
Sharp upper bounds on the \(Q\)-index of (minimally) 2-connected graphs with given size
The largest eigenvalue of a graph: A survey
Measure-theoretic bounds on the spectral radius of graphs from walks
Partitions of graphs into small and large sets
Chromatic number and signless Laplacian spectral radius of graphs
Reverse binary graphs
A spectral version of Mantel's theorem
Analytic methods for uniform hypergraphs
Lower bounds on the clique-chromatic numbers of some distance graphs
The \(p\)-spectral radius of \(k\)-partite and \(k\)-chromatic uniform hypergraphs
New bounds for the clique-chromatic numbers of Johnson graphs
A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size
New analytical lower bounds on the clique number of a graph
On completely positive graphs and their complements
Walks and the spectral radius of graphs
The rate of growth of the minimum clique size of graphs of given order and chromatic number
Lower estimate of clique size via edge coloring
Clique, chromatic, and Lovász numbers of certain circulant graphs
On Cliques and Clique Chromatic Numbers in Line, Lict and Lictact Graphs
Distance Laplacian eigenvalues and chromatic number in graphs
Signed spectral Turań-type theorems
Exact bounds on the order of the maximum clique of a graph.
Ordering graphs with given size by their signless Laplacian spectral radii
Eigenvalues and chromatic number of a signed graph
Spectral radii of graphs with given chromatic number
Counting substructures and eigenvalues. I: Triangles
A survey of automated conjectures in spectral graph theory
Remarks on the largest eigenvalue of a signed graph
Chromatic number versus chromatic number in graphs with bounded clique number

This page was built for publication: Lower bounds for the clique and the chromatic numbers of a graph

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