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

DOI10.7151/DMGT.2358zbMATH Open1504.05100arXiv1812.02613OpenAlexW2902384493MaRDI QIDQ2107750FDOQ2107750

Authors: Clive Elphick, David Anekstein, Pawel Wocjan 

Publication date: 2 December 2022

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

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)$.

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

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

zbMATH Keywords

spectral boundsvector chromatic number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• More tales of Hoffman: bounds for the vector chromatic number of a graph
• 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
• Symmetry and asymmetry between positive and negative square energies of graphs
• New eigenvalue bound for the fractional chromatic number

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)