Some relations between rank, chromatic number and energy of graphs

The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. Let G be a graph of order n and be the rank of the adjacency matrix of G. In this paper we characterize all graphs with . Among other results we show that apart from a few families of graphs, , where n is the number of vertices of G, and χ(G) are the complement and the chromatic number of G, respectively. Moreover some new lower bounds for E(G) in terms of are given.     

Some relations among term rank, clique number and list chromatic number of a graph

Let G be a graph with a nonempty edge set, we denote the rank of the adjacency matrix of G and term rank of G, by rk(G) and Rk(G), respectively. van Nuffelen conjectured that for any graph G, χ(G)?rk(G). The first counterexample to this conjecture was obtained by Alon and Seymour. In 2002, Fishkind and Kotlov proved that for any graph G, χ(G)?Rk(G). Here we improve this upper bound and show that χ_l(G)?(rk(G)+Rk(G))/2, where χ_l(G) is the list chromatic number of G.     

The chromatic number and rank of the complements of the Kasami graphs

We determine the rank and chromatic number of the complements of all Kasami graphs, some of which form an infinite family of counterexamples to the now disproven rank-coloring conjecture.     

Rank,term rank and chromatic number of a graph

Let G be a graph with a nonempty edge set, we denote the rank of the adjacency matrix of G and the term rank of G, by $\mathrm{rk}(G)$ and $\mathrm{Rk}(G)$, respectively. It was conjectured [C. van Nuffelen, Amer. Math. Monthly 83 (1976) 265–266], for any graph G, $\chi (G)?\mathrm{rk}(G)$. The first counterexample to this conjecture was obtained by Alon and Seymour [J. Graph Theor. 13 (1989) 523–525]. Recently, Fishkind and Kotlov [Discrete Math. 250 (2002) 253–257] have proved that for any graph G, $\chi (G)?\mathrm{Rk}(G)$. In this Note we improve Fishkind–Kotlov upper bound and show that $\chi (G)?\frac{\mathrm{rk}(G)+\mathrm{Rk}(G)}{2}$. To cite this article: S. Akbari, H.-R. Fanaï, C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

The chromatic number of 5-valent circulants

A circulant C(n;S) with connection set S={a₁,a₂,…,a_m} is the graph with vertex set Z_n, the cyclic group of order n, and edge set E={{i,j}:|i−j|∈S}. The chromatic number of connected circulants of degree at most four has been previously determined completely by Heuberger [C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003) 153-169]. In this paper, we determine completely the chromatic number of connected circulants C(n;a,b,n/2) of degree 5. The methods used are essentially extensions of Heuberger’s method but the formulae developed are much more complex.     

Distance graphs with maximum chromatic number

The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K₄.     

On the chromatic number of random graphs

In this paper we consider the classical Erdős–Rényi model of random graphs G_n,p. We show that for p=p(n)n^−3/4−δ, for any fixed δ>0, the chromatic number χ(G_n,p) is a.a.s. ℓ, ℓ+1, or ℓ+2, where ℓ is the maximum integer satisfying 2(ℓ−1)log(ℓ−1)p(n−1).     

On the chromatic number of circulant graphs

Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(Z_N,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on Z_N with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs.     

The chromatic number of infinite graphs — A survey

We survey some old and new results on the chromatic number of infinite graphs.     

A note on the chromatic number of a dense random graph

Let G_n,p denote the random graph on n labeled vertices, where each edge is included with probability p independent of the others. We show that for all constant p

     

Three new upper bounds on the chromatic number

This paper introduces three new upper bounds on the chromatic number, without making any assumptions on the graph structure. The first one, ξ, is based on the number of edges and nodes, and is to be applied to any connected component of the graph, whereas ζ and η are based on the degree of the nodes in the graph. The computation complexity of the three-bound computation is assessed. Theoretical and computational comparisons are also made with five well-known bounds from the literature, which demonstrate the superiority of the new upper bounds.