“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 7676
School of Mathematics
  Title:   Some relations among term rank, clique number and list chromatic number of a graph
1.  S. Akbari
2.  H. R. Fanai
  Status:   Published
  Journal: Discrete Math.
  Vol.:  306
  Year:  2006
  Pages:   3078-3082
  Supported by:  IPM
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
scroll left or right