Graphes n-coloriable

[theodutt]

Bonjour,

J'aimerais savoir comment montrer qu'un graphe est n-coloriable (déterminer le n) sans expérimenter ni utiliser d'ordinateur exécutant un algorithme si cela est possible.

Merci d'avance
-----

[invite9dc7b526]

Il faudrait que tu précises: sommets-coloriable ou arêtes-coloriable? et si tu parles d'un graphe général, simple, planaire, etc.

[theodutt]

Effectivement, je pensais à des sommets dans un graphe de connexité simple.

[invite9dc7b526]

pour un graphe simple quelconque (i.e. non planaire) il y a une cns pour qu'il soit 2-coloriable: il faut et il suffit que tous les circuits aient un nombre pair d'arêtes (ou de sommets). Maintenant, tester si tous les circuits d'un graphe sont pairs demande un algorithme, donc on n'évite pas l'ordinateur si le graphe est un peu grand.

Pour les graphes planaires il me semble qu'il y a des résultats sur les graphes 3-coloriables.

[A voir en vidéo sur Futura]

[Seirios]

Calculer le nombre chromatique d'un graphe est quelque chose de très difficile en général. Le fameux théorème des quatre couleurs affirme précisément que le nombre de chromatique de n'importe quel graphe planaire est au plus quatre, et c'est loin d'être un théorème facile ! Il n'y a pas de formule efficace pour calculer ce nombre en toute généralité, mais il existe des bornes intéressantes. Tu peux aller jeter un coup d’œil sur la page wiki : Graph coloring.

[invite9dc7b526]

Et j'ajoute que colorier un graphe planaire avec quatre couleurs n'est pas trivial. La démonstration de Appel et Haken procède par l'absurde et ne donne pas de méthode pour exhiber un 4-coloriage.

[Seirios]

Par contre, il est très facile de colorier un graphe planaire avec six couleurs, et avec un petit effort supplémentaire, on sait comment le colorier avec cinq couleurs.

[theodutt]

Merci à tous pour vos réponses !