Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

No description available.

Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres: cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le "m-degré" est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d −1.) Nous démontrons un résultat semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G)−b(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse b(G)>= m(G) − 1.

On associe à chaque variété algébrique définie sur R un complexe de cochaînes filtré, qui calcule la cohomologie à supports compacts et coefficients dans Z_2 de ses points réels. Ce complexe filtré est additif pour les inclusions fermées et acyclique pour la résolution des singularités, et est unique à quasi-isomorphisme filtré près. Il est représenté par la filtration duale de la filtration géométrique sur les chaînes semi-algébriques à supports fermés définie par McCrory and Parusiński, et induit une suite spectrale qui calcule la filtration par le poids sur la cohomologie à supports compacts. Cette suite spectrale est un invariant naturel qui contient les nombres de Betti virtuels. On montre que le produit cartésien de deux variétés nous permet de comparer le produit de leurs complexe de poids et suite spectrale respectifs avec ceux du produit, et on prouve que les produits cap et cup en cohomologie et homologie sont filtrés par rapport à ces filtrations par le poids réelles. / We associate to each algebraic variety defined over R a filtered cochain complex, which computes the cohomology with compact supports and Z_2-coefficients of the set of its real points. This filtered complex is additive for closed inclusions and acyclic for resolution of singularities, and is unique up to filtered quasi-isomorphism. It is represented by the dual filtration of the geometric filtration on semialgebraic chains with closed supports defined by McCrory and Parusiński, and leads to a spectral sequence which computes the weight filtration on cohomology with compact supports. This spectral sequence is a natural invariant which contains the additive virtual Betti numbers. We then show that the cross product of two varieties allows us to compare the product of their respective weight complexes and spectral sequences with those of their product, and prove that the cup and cap products in cohomology and homology are filtered with respect to the real weight filtrations.