2012/09/14 by Paweł Wocjan, Wocjan, Pawel, Clive Elphick +1 · 2 citations
Engineering · Computer Science · Mathematics · #graph theory and CDMA systems #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1209.3190
The purpose of this article is to improve existing lower bounds on the\nchromatic number chi. Let mu1,...,mun be the eigenvalues of the adjacency\nmatrix sorted in non-increasing order.\n First, we prove the lower bound chi >= 1 + maxm sumi=1m mui / -\nsumi=1m mun-i+1 for m=1,...,n-1. This generalizes the Hoffman lower\nbound which only involves the maximum and minimum eigenvalues, i.e., the case\nm=1. We provide several examples for which the new bound exceeds the sc\nHoffman lower bound.\n Second, we conjecture the lower bound chi >= 1 + S+ / S-, where S+ and S-\nare the sums of the squares of positive and negative eigenvalues, respectively.\nTo corroborate this conjecture, we prove the weaker bound chi >= S+/S-. We\nshow that the conjectured lower bound is tight for several families of graphs.\nWe also performed various searches for a counter-example, but none was found.\n Our proofs rely on a new technique of converting the adjacency matrix into\nthe zero matrix by conjugating with unitary matrices and use majorization of\nspectra of self-adjoint matrices.\n We also show that the above bounds are actually lower bounds on the\nnormalized orthogonal rank of a graph, which is always less than or equal to\nthe chromatic number. The normalized orthogonal rank is the minimum dimension\nmaking it possible to assign vectors with entries of modulus one to the\nvertices such that two such vectors are orthogonal if the corresponding\nvertices are connected.\n All these bounds are also valid when we replace the adjacency matrix A by W *\nA where W is an arbitrary self-adjoint matrix and * denotes the Schur product,\nthat is, entrywise product of W and A.\n