“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 | |||||
