Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Coloration de liste
Résumé
vignette|301x301px| Une instance de coloration de liste du graphe biparti complet K 3,27 avec trois couleurs par sommet. Pour tout choix de couleurs des trois sommets centraux, l'un des 27 sommets extérieurs ne peut être coloré, ce qui montre que le nombre chromatique de liste de K 3,27 est au moins quatre.
En théorie des graphes, la coloration de liste est une coloration des sommets d'un graphe où la couleur de chaque sommet est restreinte à une liste de couleurs autorisées. Elle a été étudiée pour la première fois dans les années 1970 dans des articles indépendants par Vadim G. Vizing et par Paul Erdős, et Herbert Taylor
Étant donné un graphe G et un ensemble de couleurs pour chaque sommet s (appelé sa liste), une coloration de liste est une fonction qui assigne à chaque sommet s à une couleur de la liste . Comme pour la coloration usuelle des graphes, une coloration de liste est généralement supposée propre, ce qui signifie que deux sommets adjacents n'ont pas la même couleur. Un graphe est k-choisissable (ou k-coloriable par liste) s'il admet une coloration de liste propre, quelle que soit la manière dont on attribue des listes de k couleurs à chaque sommet. La choisissabilité (ou coloriabilité de liste ou lindice chromatique de liste ) ch( G ) d'un graphe G est le plus petit nombre k tel que G soit k-choisissable.
Plus généralement, pour une fonction affectant un entier positif à chaque sommet , un graphe G est -choisissable (ou -coloriable par liste ) s'il a une coloration de liste quelle que soit l'affectation d'une liste de couleurs à chaque sommet . En particulier, si pour tous les sommets , alors la -choisissabilité correspond à la k-choisissabilité.
On considère le graphe bipartite complet à six sommets A, B, W, X, Y, Z dont la partition est composée de A et B et de W, X, Y et Z d'autre part ; les sommets A et B sont connectés à tous les sommets W, X, Y et Z, et il n'y a pas d'autres arêtes. En tant que graphe biparti, l'indice chromatique habituel de G est 2 : on peut colorer A et B d'une même couleur et W, X, Y, Z d'une même autre couleurs ; ainsi deux sommets adjacents n'ont pas la même couleur.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.