Rank, term rank and chromatic number of a graph - 01/01/04
pages | 4 |
Iconographies | 0 |
Vidéos | 0 |
Autres | 0 |
Abstract |
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 . To cite this article: S. Akbari, H.-R. Fanaï, C. R. Acad. Sci. Paris, Ser. I 340 (2005).
Le texte complet de cet article est disponible en PDF.Résumé |
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 . Pour citer cet article : S. Akbari, H.-R. Fanaï, C. R. Acad. Sci. Paris, Ser. I 340 (2005).
Le texte complet de cet article est disponible en PDF.Plan
Vol 340 - N° 3
P. 181-184 - février 2005 Retour au numéroBienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?