“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 7676  


Abstract:  
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. C. Van Nuffelen conjectured that for any
graph G, χ(G) ≤ rk(G). The first counter example 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
χ_{1}(G) ≤ [(rk(G)+Rk(G))/2] where χ_{1}(G) is the list
chromatic number of G.
Download TeX format 

back to top 