“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
  Author(s): 
1.  S. Akbari
2.  H. R. Fanai
  Status:   Published
  Journal: Discrete Math.
  Vol.:  306
  Year:  2006
  Pages:   3078-3082
  Supported by:  IPM
  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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right