BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let χ(G) denote the chromatic number of a graph and χv(G) denote the vector chromatic number. For all graphs χv(G)≤χ(G) and for some graphs χv(G)≪χ(G). Galtman proved that Hoffman's well-known lower bound for χ(G) is in fact a lower bound for χv(G). We prove that two more spectral lower bounds for χ(G) are also lower bounds for χv(G). We then use one of these bounds to derive a new characterization of χv(G).
We review bounds for the general Randić index, Rα=∑ij∈E(didj)α, and use the power mean inequality to prove, for example, that Rα≥mλ2α for α<0, where λ is the spectral radius of a graph. This enables us to strengthen various known lower and upper bounds for Rα and to generalise a non-spectral bound due to Bollobás \emph{et al}. We also prove that the zeroth-order general Randić index, Qα=∑i∈Vdiα≥nλα for α<0.
A well known upper bound for the spectral radius of a graph, due to Hong, is that μ12≤2m−n+1. It is conjectured that for connected graphs n−1≤s+≤2m−n+1, where s+ denotes the sum of the squares of the positive eigenvalues. The conjecture is proved for various classes of graphs, including bipartite, regular, complete q-partite, hyper-energetic, and barbell graphs. Various searches have found no counter-examples. The paper concludes with a brief discussion of the apparent difficulties of proving the conjecture in general.
Dvořák \emph{et al.} introduced a variant of the Randić index of a graph G, denoted by R′(G), where R′(G)=∑uv∈E(G)max{d(u),d(v)}1, and d(u) denotes the degree of a vertex u in G. The coloring number col(G) of a graph G is the smallest number k for which there exists a linear ordering of the vertices of G such that each vertex is preceded by fewer than k of its neighbors. It is well-known that χ(G)≤col(G) for any graph G, where χ(G) denotes the chromatic number of G. In this note, we show that for any graph G without isolated vertices, col(G)≤2R′(G), with equality if and only if G is obtained from identifying the center of a star with a vertex of a complete graph. This extends some known results. In addition, we present some new spectral bounds for the coloring and achromatic numbers of a graph.
The best degree-based upper bound for the spectral radius is due to Liu and Weng. This paper begins by demonstrating that a (forgotten) upper bound for the spectral radius dating from 1983 is equivalent to their much more recent bound. This bound is then used to compare lower bounds for the clique number. A series of sharp upper bounds for the signless Laplacian spectral radius is then proposed as another application. Finally a new lower bound for generalised r-partite graphs is proved, by extending a result due to Erdos.
In this paper, we define and compare four new measures of graph irregularity. We use these measures to prove upper bounds for the chromatic number and the Colin de Verdiere parameter. We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent Turan's theorem can be similarly strengthened for generalized r-partite graphs. We conclude by relating these new measures to the Randic index and using the measures to devise new normalised indices of network heterogeneity.
One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where mu_1 and mu_n are respectively the maximum and minimum eigenvalues of the adjacency matrix: chi >= 1 + mu_1 / (- mu_n). We recently generalised this bound to include all eigenvalues of the adjacency matrix. In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified by considering the normalized adjacency matrix, and examples are cited for which the new bounds outperform known bounds.
The purpose of this article is to improve existing lower bounds on the chromatic number chi. Let mu_1,...,mu_n be the eigenvalues of the adjacency matrix sorted in non-increasing order. First, we prove the lower bound chi >= 1 + max_m {sum_{i=1}^m mu_i / - sum_{i=1}^m mu_{n-i+1}} for m=1,...,n-1. This generalizes the Hoffman lower bound which only involves the maximum and minimum eigenvalues, i.e., the case m=1. We provide several examples for which the new bound exceeds the {\sc Hoffman} lower bound. Second, we conjecture the lower bound chi >= 1 + S^+ / S^-, where S^+ and S^- are the sums of the squares of positive and negative eigenvalues, respectively. To corroborate this conjecture, we prove the weaker bound chi >= S^+/S^-. We show that the conjectured lower bound is tight for several families of graphs. We also performed various searches for a counter-example, but none was found. Our proofs rely on a new technique of converting the adjacency matrix into the zero matrix by conjugating with unitary matrices and use majorization of spectra of self-adjoint matrices. We also show that the above bounds are actually lower bounds on the normalized orthogonal rank of a graph, which is always less than or equal to the chromatic number. The normalized orthogonal rank is the minimum dimension making it possible to assign vectors with entries of modulus one to the vertices such that two such vectors are orthogonal if the corresponding vertices are connected. All these bounds are also valid when we replace the adjacency matrix A by W * A where W is an arbitrary self-adjoint matrix and * denotes the Schur product, that is, entrywise product of W and A.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.