Veuillez utiliser cette adresse pour citer ce document : https://di.univ-blida.dz/jspui/handle/123456789/746
Affichage complet
Élément Dublin CoreValeurLangue
dc.contributor.authorIkhlef Eschouf, Noureddine-
dc.date.accessioned2019-10-13T11:40:32Z-
dc.date.available2019-10-13T11:40:32Z-
dc.date.issued2007-
dc.identifier.urihttp://di.univ-blida.dz:8080/xmlui/handle/123456789/746-
dc.description88 p.-4 CD-ROM.-ill.-30cm.fr_FR
dc.description.abstractSoit 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 cliquemaximum 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 .fr_FR
dc.language.isofrfr_FR
dc.publisheruniv- blida 1fr_FR
dc.subjectLA b-COLORATIONfr_FR
dc.subjectLES GRAPHESfr_FR
dc.titleContribution à l'etude de la b-coloration dans les graphesfr_FR
dc.typeThesisfr_FR
Collection(s) :Thèse de Magister

Fichier(s) constituant ce document :
Fichier Description TailleFormat 
32-510-22-1.pdfThése de magister850,28 kBAdobe PDFVoir/Ouvrir


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