Coloration d'un graphe théorème 4 couleurs...

[allezlolo]

Bonjour,

J'essaye depuis aujourd'hui de rassembler différentes informations afin de comprendre une partie de la théorie autour de la coloration des sommets d'un graphe.

J'ai une petit problème de compréhension au niveau d'un article trouvé sur wikipédia.
L'article en question est celui ci :
http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_quatre_couleurs

Dans la rubrique Généralisation du théorème des quatre couleurs :

il est dit

Le théorème des quatre couleurs se généralise aux graphes sans mineur K5, puisque le nombre chromatique de ces graphes vaut au plus 4 (et c'est une des motivations de la conjecture d'Hadwiger)

Je ne comprends pas exactement si cette phrase signifie :

il est pouvé qu'un graphe sans mineur k5 se colorie en 4 couleurs maximum

ou plutôt :

si la conjecture d'Hadwinger se révèle vrai alors, un graphe sans mineur k5 se colorie en 4 couleurs maximum

Dans le cas de ma remière solution, avez vous une preuve simple expliquant qu'un graphe sans mineur k5 se colorie en 4 couleurs max ?


Merci d'avance pour votre aide

[Clembou]

Bonjour,

J'essaye depuis aujourd'hui de rassembler différentes informations afin de comprendre une partie de la théorie autour de la coloration des sommets d'un graphe.

J'ai une petit problème de compréhension au niveau d'un article trouvé sur wikipédia.
L'article en question est celui ci :
http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_quatre_couleurs

Dans la rubrique Généralisation du théorème des quatre couleurs :

il est dit

Je ne comprends pas exactement si cette phrase signifie :



ou plutôt :



Dans le cas de ma remière solution, avez vous une preuve simple expliquant qu'un graphe sans mineur k5 se colorie en 4 couleurs max ?


Merci d'avance pour votre aide

Quand on dit "colorier un graphe de 4 couleurs", on veut en fait qu'avec 4 couleurs, on peut trouver un chemin tel que on ne trouve pas deux couleurs identiques.

Pour , tu peux mettre 4 couleurs sur 4 sommets et une des 4 couleurs sur le sommet restant et essaie de trouver un chemin qui utilise toutes les arrêtes de , tu verras qu'il restera toujours l'arrête qui relie le sommet bleu à l'autre sommet bleu... (par exemple)

[allezlolo]

merci c'est bien ce que j'avais compris.

Du coup si je comprends bien la conjecture d'Hadwinger dit que si Kk n'est pas un mineur d'un graphe G alors celui ci peut-être colorier en k-1 couleur.

Si cette conjecture se révéler vrai, cela signifie que pour colorier n'importe qu'elle graphe G on pourrait appliquer l'algorithme grossier suivante :

debut
repérer le plus grand degré noté k.
On note k se degré :
Si Kk est un mineur de ce graphe,
alors on peut colorier le graphe en k-1 couleurs maximum.
autrement
on recherche le plus grand degré suivant k.
fsi
fin

Suis je dans le vrai ?

merci de votre aide...

[jahlucine]

J'ai l'impression que tu n'as pas tout saisi concernant les graphes.

Qu'un graphe ait ou pas un mineur Kk, n'a pas de relation directe triviale avec le degre des sommets.
Tu cherches a ecrire une demonstration ou un algorithme de coloriage?
Si c'est un algorithme alors il faut faire ca :

Faire des contractions successives jusqu'a trouver le plus grand k tel que Kk soit un mineur du graphe
Chercher un coloriage en k-1 couleurs.

La conjecture d hadwiger (et pas hadwinger) est verifiee jusqu'a 6, donc a priori tu peux etre tranquille si ton graphe est pas trop gros.