Rank, term rank and chromatic number of a graph

Soit G un graphe avec un ensemble d'arête non vide. On note rk(G) le rang (réel) d'une matrice d'adjacence A de G et Rk(G) le rang maximal d'une matrice ayant même support que A. Il a été conjecturé [C. van Nuffelen, Amer. Math. Monthly 83 (1976) 265-266] que pour tout graphe G, χ(G)⩽rk(G). Le premier contre-exemple à cette conjecture a été obtenu par Alon et Seymour [J. Graph Theor. 13 (1989) 523-525]. Récemment, Fishkind et Kotlov [Discrete Math. 250 (2002) 253-257] ont montré que pour tout graphe G, χ(G)⩽Rk(G). Dans cette Note, nous améliorons cette borne et montrons χ(G)⩽rk(G)+Rk(G)2. Pour citer cet article : S. Akbari, H.-R. Fanaï, C. R. Acad. Sci. Paris, Ser. I 340 (2005).