More tales of Hoffman: bounds for the vector chromatic number of a graph

DOI10.7151/DMGT.2358zbMATHOpenAlexMaRDI QIDQ2107750FDO

Authors Clive Elphick, David Anekstein, Pawel Wocjan

Publication date 2 December 2022

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

spectral boundsvector chromatic number

Mathematics Subject Classification ID

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

Abstract: Let $chi(G)$ denote the chromatic number of a graph and $ch{i}_v(G)$ denote the vector chromatic number. For all graphs $ch{i}_v(G)lechi(G)$ and for some graphs $ch{i}_v(G)llchi(G)$. Galtman proved that Hoffman's well-known lower bound for $chi(G)$ is in fact a lower bound for $ch{i}_v(G)$. We prove that two more spectral lower bounds for $chi(G)$ are also lower bounds for $ch{i}_v(G)$. We then use one of these bounds to derive a new characterization of $ch{i}_v(G)$.

Recommendations

• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Spectral lower bounds for the quantum chromatic number of a graph. II
• A lower bound for the chromatic number of a graph
• Eigenvalues and chromatic number of a signed graph

Cites work

• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• scientific article; zbMATH DE number 967931 (Why is no real title available?)
• Approximate graph coloring by semidefinite programming
• Chromatic number and spectral radius
• Graph homomorphisms via vector colorings
• Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
• Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory
• Matrix inequalities
• More tales of Hoffman: bounds for the vector chromatic number of a graph
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• On the Shannon capacity of a graph
• Proof of a conjectured lower bound on the chromatic number of a graph
• Sabidussi versus Hedetniemi for three variations of the chromatic number
• Spectral characterizations of the Lovász number and the Delsarte number of a graph
• Spectral lower bounds for the orthogonal and projective ranks of a graph
• Spectral lower bounds for the quantum chromatic number of a graph
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• The smallest eigenvalue of the signless Laplacian
• Unified spectral bounds on the chromatic number

Cited in

(11)

• Spectral bounds for the independence ratio and the chromatic number of an operator
• Symmetry and asymmetry between positive and negative square energies of graphs
• Spectral lower bounds for the quantum chromatic number of a graph. II
• New eigenvalue bound for the fractional chromatic number
• Spectral lower bounds for the orthogonal and projective ranks of a graph
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• More tales of Hoffman: bounds for the vector chromatic number of a graph
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• An inertial lower bound for the chromatic number of a graph
• Weighted graphs: eigenvalues and chromatic number
• Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming

This page was built for publication: More tales of Hoffman: bounds for the vector chromatic number of a graph

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