“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 7720
School of Mathematics
  Title:   Rank, term rank and chromatic number of a graph
1.  S. Akbari
2.  H.R. Fanai
  Status:   Published
  Journal: C. R. Acad. Sci. Paris. Ser. I
  Vol.:  340
  Year:  2005
  Pages:   181-184
  Supported by:  IPM
Let G be a graph with nonempty edge set, we denote the rank of the adjacency matrix of G, by rk(G) and Rk(G), respectively. It was conjectured [4], for any graph G,χ(G) ≤ rk(G). The first counterexample to this conjecture was obtained by Alon and Seymour [1]. Recently, Fishkind and Kotlov [3] have proved that for any graph G,χ(G) ≤ Rk(G). In this paper, we improve Fishkind-Kotlov upper bound and show that χ(G) ≤ [(rk(G)+Rk(G))/2].

Download TeX format
back to top
scroll left or right