DSpace JSPUI

1. Université Saad Dahlab blida 1
2. Bibliothèque Universitaire Centrale
3. Thèse de Magister

Titre:	Contribution à l'etude de la b-coloration dans les graphes
Auteur(s):	Ikhlef Eschouf, Noureddine
Mots-clés:	b-COLORATION LES GRAPHES
Date de publication:	2007
Editeur:	univ- blida 1
Résumé:	Soit G = (V; E) un graphe simple díordre n o˘ V est líensemble des sommets et E líensemble des arÍtes. On dÈsigne par !(G) et ￿(G) respectivement la taille díune clique maximum de G et la taille díun couplage maximum de G.Parmi les nombreux paramËtres de coloration existants, on a ÈtudiÈ un nouveau concept de coloration des sommets, appelÈ coloration dominante ou b￿coloration. La coloration propre des sommets est une attribution de couleurs aux sommets de G de telle sorte que deux sommets adjacents aient toujours des couleurs di§Èrentes. Le nombre chromatique, notÈ ￿(G); est le nombre minimum de couleurs pour lequel G admet une coloration propre. La coloration dominante est une coloration propre telle que toute classe de couleur contient un sommet adjacent ‡ au moins un sommet de chaque classe de couleur autre que la sienne. Le nombre b￿chromatique, notÈ b(G), est le nombre maximum de classes de couleurs dans une coloration dominante. Une k￿coloration de Grundy díun graphe G est une coloration propre utilisant k couleurs vÈriÖant la propriÈtÈ suivante : chaque sommet v, colorÈ par une couleur i ; 1 ￿ i ￿ k; doit Ítre adjacent ‡ au moins i ￿ 1 sommets colorÈs par chacune des couleurs j telles que 1 ￿ j ￿ i ￿ 1: Le nombre de Grundy díun graphe G, notÈ ￿(G); est le nombre maximum de couleurs nÈcessaires pour une coloration de Grundy de G. Dans ce mÈmoire, on prÈsente deux nouvelles bornes pour le nombre b￿chromatique en fonction de n; ! et ￿: On caractÈrise par la suite les graphes bipartis dont le nombre b(G) = n=2 ou (n + 1)=2 et les graphes tels que b(G) ￿ ￿(G) = n=2 ou (n ￿ 1)=2: On dÈtermine la valeur exacte du nombre b￿chromatique du produit croisÈ de certains arbres particuliers, on montre aussi que ces graphes sont b￿continus. Un graphe G est dit b￿continu síil admet une b￿coloration avev k couleurs pour tout k, ￿(G) ￿ k ￿ b(G): AprËs avoir remarquer que les deux paramËtres b(G) et ￿(G) sont en gÈnÈral incomparables, on montre que, si G est sans P4 alors b(G) ￿ ￿(G). On montre aussi que le paramËtre b(G) peut Ítre calculÈ en temps polynomial dans cette classe de graphes. EnÖn, on Ètablit un thÈorËme qui caractÈrise les graphes tels que b(H) = ￿(H) pour tout sous graphe induit H de G .
Description:	88 p.- 4 CD-ROM.-ill.-30cm.
URI/URL:	http://di.univ-blida.dz:8080/xmlui/handle/123456789/741
Collection(s) :	Thèse de Magister

Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.