Let G be a graph with a nonempty edge set, we denote the rank of the adjacency matrix of G and the term rank of G, by and , respectively. It was conjectured [C. van Nuffelen, Amer. Math. Monthly 83 (1976) 265–266], for any graph G, . The first counterexample to this conjecture was obtained by Alon and Seymour [J. Graph Theor. 13 (1989) 523–525]. Recently, Fishkind and Kotlov [Discrete Math. 250 (2002) 253–257] have proved that for any graph G, . In this Note we improve Fishkind–Kotlov upper bound and show that .
Soit G un graphe avec un ensemble d'arête non vide. On note le rang (réel) d'une matrice d'adjacence A de G et 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, . 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, . Dans cette Note, nous améliorons cette borne et montrons .
Accepted:
Published online:
@article{CRMATH_2005__340_3_181_0, author = {Akbari, Saieed and Fana{\"\i}, Hamid-Reza}, title = {Rank, term rank and chromatic number of a graph}, journal = {Comptes Rendus. Math\'ematique}, pages = {181--184}, publisher = {Elsevier}, volume = {340}, number = {3}, year = {2005}, doi = {10.1016/j.crma.2004.12.003}, language = {en}, url = {http://archive.numdam.org/articles/10.1016/j.crma.2004.12.003/} }
TY - JOUR AU - Akbari, Saieed AU - Fanaï, Hamid-Reza TI - Rank, term rank and chromatic number of a graph JO - Comptes Rendus. Mathématique PY - 2005 SP - 181 EP - 184 VL - 340 IS - 3 PB - Elsevier UR - http://archive.numdam.org/articles/10.1016/j.crma.2004.12.003/ DO - 10.1016/j.crma.2004.12.003 LA - en ID - CRMATH_2005__340_3_181_0 ER -
%0 Journal Article %A Akbari, Saieed %A Fanaï, Hamid-Reza %T Rank, term rank and chromatic number of a graph %J Comptes Rendus. Mathématique %D 2005 %P 181-184 %V 340 %N 3 %I Elsevier %U http://archive.numdam.org/articles/10.1016/j.crma.2004.12.003/ %R 10.1016/j.crma.2004.12.003 %G en %F CRMATH_2005__340_3_181_0
Akbari, Saieed; Fanaï, Hamid-Reza. Rank, term rank and chromatic number of a graph. Comptes Rendus. Mathématique, Volume 340 (2005) no. 3, pp. 181-184. doi : 10.1016/j.crma.2004.12.003. http://archive.numdam.org/articles/10.1016/j.crma.2004.12.003/
[1] A Counterexample to the rank-coloring conjecture, J. Graph Theor., Volume 13 (1989), pp. 523-525
[2] The rank and size of graphs, J. Graph Theor., Volume 23 (1996), pp. 185-189
[3] Rank, term rank, and chromatic number, Discrete Math., Volume 250 (2002), pp. 253-257
[4] A bound for the chromatic number of a graph, Amer. Math. Monthly, Volume 83 (1976), pp. 265-266
[5] Fractional Graph Theory, A Rational Approach to the Theory of Graphs, Wiley, New York, 1997
Cited by Sources: