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

Dominik Janzing; Pawel Wocjan; Thomas Beth (Universitaet Karlsruhe)

arxiv: cs/0112023 · v1 · submitted 2001-12-21 · 💻 cs.DM · quant-ph

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

Pawel Wocjan , Dominik Janzing , Thomas Beth (Universitaet Karlsruhe) This is my paper

classification 💻 cs.DM quant-ph

keywords matricesadjacencyboundchromaticlowernumberspectraweighted

0 comments

read the original 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.

This paper has not been read by Pith yet.

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

discussion (0)