“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 7720 |
|
||||
| Abstract: | |||||
|
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 | |||||
