Coloriable

"coloriable" dans l'encyclopédie

• GRAPHES PARFAITS THÉORÈME FORT DES

  • Écrit par Vincent BARRÉ
  • 3 886 mots

  Par exemple, un cycle (graphe dont les sommets sont reliés uniquement à leur prédécesseur et leur successeur) est coloriable en 2 (nombre pair de sommets) ou 3 (nombre impair de sommets) couleurs. Le graphe précédent est un graphe d'intervalle et fait partie de la famille des graphes parfaits introduite par le Français Claude Berge (1926-2002) au début des années 1960.

• QUATRE COULEURS PROBLÈME DES

  • Écrit par Jean MAYER
  • 11 961 mots
  • 2 médias

   Heawood (1890) prouvât l'illégitimité de cette double modification, en signalant de plus que l'argument de Kempe suffisait à démontrer le théorème des cinq couleurs, résultat plus faible (tout graphe planaire sans boucles est coloriable avec cinq couleurs). La théorie des réductions, étudiée systématiquement par de nombreux auteurs (le travail fondamental a été accompli en particulier par H.

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD, Philippe FLAJOLET
  • 36 583 mots
  • 3 médias

  Il a été montré, en revanche, que tout graphe planaire est coloriable avec au plus quatre couleurs. – Programmation en nombres entiers : On doit à Lenstra (1981) un algorithme qui, pour un nombre fixé de variables, permet de résoudre la programmation en nombres entiers en un temps polynomial (le degré du polynôme étant fonction du nombre de variables).