thesis

La b-continuite des b-colorations : complexité, propriétés structurelles et algorithmes

Defense date:

Jan. 1, 2005

Edit

Institution:

Paris 11

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

THE B-COLORING OF A GRAPH G IS A COLORING SUCH OF G SUCH THAT FOR EACH COLOR c, THERE EXISTS AT LEAST A VERTEX v (CALLED COLORFUL VERTEX) COLORED c HAVING EACH OTHER COLOR ON ITS NEIGHBORHOOD. AN F-COLORING IS A B-COLORING WHERE ALL THE VERTICES ARE COLORFUL. IT IS CLEAR THAT ANY COLORING WITH THE CHROMATIC NUMBER OF COLORS IS A B-COLORING. WHOEVER, THE F-COLORING DO NOT EXIST IN ANY GRAPH. ^ONE PECULIAR CHARACTERISTIC OF B-COLORINGS (RESP; F-COLORINGS) IS THAT FOR SOME GRAPHS, THERE EXISTS A p AND A q B-COLORING (RESP. F-COLORING) WITH p<q, BUT THERE IS NO B-COLORINGS (RESP; F-COLORINGS) WITH k COLORS WITH p<k<q. WE SAY THAT SUCH A GRAPH IS NOT B-CONTINUOUS (RESP. F-CONTINUOUS). IN THESES WE DEAL WITH THE B-CONTINUITY (RESP. THE F-CONTINUITY). WE ANSWER SOME NATURELS OPEN QUESTIONS ON THIS SUBJECT. S

Abstract FR:

LA B-COLORATION D'UN GRAPHE G EST UNE COLORATION TELLE QUE POUR CHAQUE COULEUR c, IL EXISTE AU MOINS UN SOMMET v COLORE c DONT LE VOISINAGE EST COLORE PAR TOUTES LES AUTRES COULEURS. LE SOMMET v EST DIT UN SOMMET B-CHROMATIQUE. UNE F-COLORATION EST UNE B-COLORATION OU TOUS LES SOMMETS SONT B-CHROMATIQUEUNE COLORATION AVEC LE NOMBRE CHROMATIQUE EST UNE B-COLORATION, EN REVANCHE IL EXITE DES GRAPHES QUI N'ADMETTES AUCUNE F-COLORATIONS. CONTRAIREMENT A TOUTES LES AUTRES COLORATIONS, IL PEUT EXISTER UNE B-COLORATION D'UN GRAPHE AVEC p COULEURS ET UNE AUTRE AVEC q COULEURS (p<q) ALORS QU'IL N'EXISTE AUCUNE B-COLORATIONS INTERMEDIAIRE. DE MEME POUR LA F-COLORATION. ON APPELLE LE B-SPECTRE (RESP. LE F-SPECTRE) D'UN GRAPHE G, L'ENSEMBLE DES ENTIERS K POUR LESQULES G ADMET UNE B-COLORATION (F-COLORATION). SI LE B-SPECTRE (RESP. LE F-SPECTRE) EST UN INTERVALLE, ON DIT QUE G EST B-CONTINU (RESP. F-CONTINU). DANS CETTE THESE, NOUS NOUS SOMMES INTERESSES A CET ASPECT DE CONTINUITE DES B-COLORATIONS ET F-COLORATIONS D'UN GRAPHE. NOUS AVONS REPONDU A PLESIEURS QUESTIONS OUVETES SUR CE SUJET.