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

DOI10.7151/DMGT.2358MaRDI QIDQ2107750zbMATH OpenOpenAlexFDO

Authors Clive Elphick, David Anekstein, Pawel Wocjan

Publication date 2 December 2022

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

zbMATH Keywords

spectral boundsvector chromatic number

Mathematics Subject Classification ID

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

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

Review text

The authors prove bounds between parameters related to graph colouring and parameters obtained from graph spectral theory. More specifically, the authors consider two parameters of a graph \(G\) related to the eigenvalues of matrices associated with \(G\), which were obtained respectively in [\textit{L. Silva de Lima} et al., Linear Algebra Appl. 435, No. 10, 2570--2584 (2011; Zbl 1222.05180)] and in [\textit{L. Yu. Kolotilina}, J. Math. Sci., New York 176, No. 1, 44--56 (2011; Zbl 1291.15050); translation from Zap. Nauchn. Semin. POMI 382, 82--103 (2010)]. It was known that both of these parameters are lower bounds for \(\chi(G)\). The main result of this paper is that these parameters are, in fact, also lower bounds for the ``vector chromatic number \(\chi_v(G)\) introduced by \textit{D. Karger} et al. [J. ACM 45, No. 2, 246--265 (1998; Zbl 0904.68116)].

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

• 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
• 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?)
• 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

(12)

• More tales of Hoffman: bounds for the vector chromatic number of a graph
• Spectral lower bounds for the quantum chromatic number of a graph. II
• 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
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Spectral bounds for the independence ratio and the chromatic number of an operator
• Weighted graphs: eigenvalues and chromatic number
• Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming
• An inertial lower bound for the chromatic number of a graph
• New eigenvalue bound for the fractional chromatic number
• Symmetry and asymmetry between positive and negative square energies of graphs
• A spectral lower bound on chromatic numbers using p-energy

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)