Concept

Polynôme chromatique

Résumé
En mathématiques, plus particulièrement en théorie des graphes, le polynôme chromatique d'un graphe est une fonction polynômiale donnant le nombre de colorations distinctes d'un graphe, en fonction du nombre de couleurs autorisées. Il a été introduit d'abord en 1912 pour les graphes planaires, par George David Birkhoff, qui cherchait à démontrer le théorème des quatre couleurs. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs au nombre chromatique du graphe et a pour degré l'ordre du graphe. Le polynôme chromatique d'un graphe est un invariant, c'est-à-dire une propriété dépendant uniquement de sa structure et indépendante de son étiquetage. Autrement dit, deux graphes isomorphes auront le même polynôme chromatique. Le terme de chromatiquement équivalent est employé pour désigner des graphes ayant le même polynôme chromatique. À l'opposé, un graphe chromatiquement unique est déterminé par son polynôme chromatique. Soit G un graphe ayant n sommets. Notant le nombre de colorations des sommets de G avec k couleurs (distinctes), le polynôme chromatique de G, , est défini comme étant l'unique polynôme d'interpolation de degré n tel que, pour tout k avec , on ait . On a en particulier, pour tout graphe ayant plus d'une arête, , et plus précisément, le nombre chromatique de g est le plus petit entier qui n'est pas une racine de . Un théorème d'intérêt est le suivant : pour toute arête e du graphe G, où G-e est le graphe G sans l'arête e et G.e le graphe obtenu en contractant l'arête e de G. Un corollaire de ce théorème a été énoncé par George David Birkhoff en 1912 : Pour un graphe G à n nœuds, est un polynôme monique de degré n (i.e. un polynôme donc le coefficient du terme de degré n vaut 1), de terme constant nul et dont les coefficients alternent en signe. Le graphe diamant est chromatiquement unique : c'est le seul graphe à avoir comme polynôme chromatique. Il existe deux graphes chromatiquement équivalents au graphe taureau. L'un d'eux est le graphe criquet.
À 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.
Cours associés (3)
MATH-261: Discrete optimization
This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to p
PHYS-512: Statistical physics of computation
This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and
MATH-632: Semidefinite Optimization and Applications to Geometric and Combinatorial Problems
This course covers the following topics: Introduction to conic optimization, Duality in conic programming, Sums of squares/ SemideFinite relaxation for independence number and chromatic number, Harmon
Séances de cours associées (10)
Bases de programmation entières
Introduit les bases de la programmation entière, y compris les programmes binaires entiers et les stratégies de contrainte.
Etre l'entropie libre
Couvre le calcul de l'entropie libre et l'interprétation des messages entre variables et facteurs.
Théorie quantique des champs : les particules filantes
Explore la synthèse des particules en rotation et des sommets appropriés pour les fonctions à 2 points en théorie quantique des champs.
Afficher plus
Publications associées (32)