Lower Bound on the Chromatic Number by Spectra of Weighted Adjacency Matrices

2001/12/21 by Pawel Wocjan, Paweł Wocjan, Dominik Janzing +4
Computer Science · Mathematics · Physics and Astronomy · #Advanced Mathematical Theories and Applications #Algebraic and Geometric Analysis #Matrix Theory and Algorithms #cs.DM #quant-ph

paper · pdf · doi:10.48550/arxiv.cs/0112023

6 pages

arxiv created 2001/12/21 · arxiv updated 2009/11/30

Abstract

A lower bound on the chromatic number of a graph is derived by majorization of spectra of weighted adjacency matrices. These matrices are given by Hadamard products of the adjacency matrix and arbitrary Hermitian matrices.

Citations

• Simulating Arbitrary Pair-Interactions by a Given Hamiltonian: Graph-Theoretical Bounds on the Time Complexity

Related

• Unified spectral bounds on the chromatic number
• New spectral bounds on the chromatic number encompassing all eigenvalues\n of the adjacency matrix
• Sums of squares of eigenvalues and the vector chromatic number
• A Spectral Lower Bound on Chromatic Numbers using p-Energy
• Hoffman's bound for hypergraphs