Contribution à l'etude de la b-coloration dans les graphes

Ikhlef Eschouf, Noureddine

Veuillez utiliser cette adresse pour citer ce document : https://di.univ-blida.dz/jspui/handle/123456789/741

Affichage complet

Élément Dublin Core	Valeur	Langue
dc.contributor.author	Ikhlef Eschouf, Noureddine	-
dc.date.accessioned	2019-10-13T11:27:46Z	-
dc.date.available	2019-10-13T11:27:46Z	-
dc.date.issued	2007	-
dc.identifier.uri	http://di.univ-blida.dz:8080/xmlui/handle/123456789/741	-
dc.description	88 p.- 4 CD-ROM.-ill.-30cm.	fr_FR
dc.description.abstract	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 bcoloration. 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 bchromatique, notÈ b(G), est le nombre maximum de classes de couleurs dans une coloration dominante. Une kcoloration 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 bchromatique 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 bchromatique du produit croisÈ de certains arbres particuliers, on montre aussi que ces graphes sont bcontinus. Un graphe G est dit bcontinu síil admet une bcoloration 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.iso	fr	fr_FR
dc.publisher	univ- blida 1	fr_FR
dc.subject	b-COLORATION	fr_FR
dc.subject	LES GRAPHES	fr_FR
dc.title	Contribution à l'etude de la b-coloration dans les graphes	fr_FR
dc.type	Thesis	fr_FR
Collection(s) :	Thèse de Magister

Fichier(s) constituant ce document :

Fichier	Description	Taille	Format
32-510-22-1.pdf	Thése de magister	850,28 kB	Adobe PDF	Voir/Ouvrir

Affichage abbrégé

DSpace JSPUI

DSpace préserve et permet l'accès à toute manière de contenu, y compris des documents texte, des images, des MPEG et des ensembles de données