L’extrait ci-dessous de Wikipédia n’est pas soutenu par une source fiable. Pouvez-vous en trouver une ?
Cliquez sur J’ai compris ! pour aller sur Wikipédia et corriger le fragment de code ou Suivant ! pour en voir un autre. Bonne chance !
Sur la page Coloration de graphe :
"Il existe des algorithmes polynomiaux si on se restreint à des classes de graphes.
- Les graphes triangulés sont des graphes parfaits. Un résultat nettement plus difficile (de László Lovász et al.) établit (en développant toute une théorie) que l'on peut déterminer en temps polynomial le nombre chromatique de tout graphe parfait (pour une définition voir Théorème des graphes parfaits)[réf. nécessaire].
- pour les graphes planaires, le théorème des quatre couleurs permet de décider l'existence d'une k-coloration dès que k est plus grand que 4 (en temps constant car il en existe toujours une). De plus, on sait trouver une telle 4-coloration en temps quadratique[réf. nécessaire]. Par contre, le problème reste NP-complet pour k = 3[réf. nécessaire].
Vous pouvez personnaliser Chasse à la citation en fournissant une liste d’articles. Cela vous fournira un lien que vous pourrez partager avec d’autres pour qu’ils puissent naviguer dans Chasse à la citation en étant limités aux articles que vous avez fournis.
Comment aimeriez-vous créer un Chasse à la citation personnalisé ?
Utiliser la boîte de recherche ci-dessous pour trouver et ajouter des articles à votre Chasse à la citation personnalisé. Vous pouvez supprimer un article en cliquant dessus dans l’aperçu ci-dessous.
Veuillez entrer les titres d’article de Wikipédia à importer, un par ligne, dans la zone ci-dessous :
PetScan est un outil pour interroger Wikipedia et définir des listes d’articles. PetScan assigne des IDs aux requêtes afin que leurs résultats puissent être importés dans d’autres outils.
Veuillez créer votre requête dans PetScan et coller son identifiant ci-dessous :
Pagepile est un outil permettant de définir des listes d'articles Wikipédia. Pagepile attribue des identifiants aux listes afin que leurs résultats puissent être importés dans d'autres outils.
Veuillez créer votre liste dans Pagepile et coller son identifiant ci-dessous :
Veuillez patienter, votre Chasse à la citation personnalisé est en train d’être calculé. Cela peut prendre quelques minutes...
Vous pouvez appuyer sur Retour ou fermer cette boîte de dialogue pour annuler.
Votre Chasse à la citation personnalisé a été créé !
Vous pouvez copier et partager le lien ci-dessus pour permettre à d’autres personnes de l’utiliser ou pour le consulter maintenant !
Désolé, votre personnalisation de Chasse à la citation a échoué lors de sa création ou s’est avérée vide !
Veuillez réessayer et garder à l’esprit les recommandations suivantes :