no. 3
Combinatorics
Rank, term rank and chromatic number of a graph
[Rang, rang maximal et nombre chromatique d'un graphe]

Présenté par : Étienne Ghys

Akbari, Saieed1, 2 ; Fanaï, Hamid-Reza1, 2
1 Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran
2 Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11365-9415, Tehran, Iran
Comptes Rendus. Mathématique, Tome 340 (2005) no. 3, pp. 181-184.

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.

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 rk(G) and Rk(G), respectively. It was conjectured [C. van Nuffelen, Amer. Math. Monthly 83 (1976) 265–266], for any graph G, χ(G)⩽rk(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, χ(G)⩽Rk(G). In this Note we improve Fishkind–Kotlov upper bound and show that χ(G)⩽rk(G)+Rk(G)2.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2004.12.003
Akbari, Saieed 1, 2 ; Fanaï, Hamid-Reza 1, 2

1 Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran
2 Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11365-9415, Tehran, Iran 
@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://www.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://www.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://www.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, Tome 340 (2005) no. 3, pp. 181-184. doi : 10.1016/j.crma.2004.12.003. http://www.numdam.org/articles/10.1016/j.crma.2004.12.003/

[1] Alon, N.; Seymour, P. A Counterexample to the rank-coloring conjecture, J. Graph Theor., Volume 13 (1989), pp. 523-525

[2] Kotlov, A.; Lovász, L. The rank and size of graphs, J. Graph Theor., Volume 23 (1996), pp. 185-189

[3] Fishkind, D.E.; Kotlov, A. Rank, term rank, and chromatic number, Discrete Math., Volume 250 (2002), pp. 253-257

[4] van Nuffelen, C. A bound for the chromatic number of a graph, Amer. Math. Monthly, Volume 83 (1976), pp. 265-266

[5] Scheinerman, E.R.; Ulman, D.H. Fractional Graph Theory, A Rational Approach to the Theory of Graphs, Wiley, New York, 1997

Cité par Sources :