Rank, term rank and chromatic number of a graph

Saieed Akbari; Hamid-Reza Fanaï

doi:10.1016/j.crma.2004.12.003

Combinatorics

Rank, term rank and chromatic number of a graph

Presented by: Étienne Ghys

Saieed Akbari ^1,²; Hamid-Reza Fanaï ^1,²

¹ Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran
² Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11365-9415, Tehran, Iran

Comptes Rendus. Mathématique, Volume 340 (2005) no. 3, pp. 181-184.

Abstract
Résumé

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) ⩽ \frac{rk (G) + Rk (G)}{2}$ .

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) ⩽ \frac{rk (G) + Rk (G)}{2}$ .

Received: 2004-11-13
Accepted: 2004-11-27
Published online: 2005-01-05

DOI: 10.1016/j.crma.2004.12.003

Author's affiliations:

Saieed Akbari ^{1, 2}; Hamid-Reza Fanaï ^{1, 2}

¹ Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran
² Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11365-9415, Tehran, Iran

@article{CRMATH_2005__340_3_181_0,
     author = {Saieed Akbari and Hamid-Reza Fana{\"\i}},
     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},
}

TY  - JOUR
AU  - Saieed Akbari
AU  - Hamid-Reza Fanaï
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
DO  - 10.1016/j.crma.2004.12.003
LA  - en
ID  - CRMATH_2005__340_3_181_0
ER  -

%0 Journal Article
%A Saieed Akbari
%A Hamid-Reza Fanaï
%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
%R 10.1016/j.crma.2004.12.003
%G en
%F CRMATH_2005__340_3_181_0

Saieed Akbari; Hamid-Reza Fanaï. 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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.12.003/

References
Cited by

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

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

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

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

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

Cited by Sources:

Comments - Policy