Familles de graphes possédant des algorithmes polynomiaux de temps pour calculer le nombre chromatique

Message mis à jour le 31 août : j'ai ajouté un résumé des réponses actuelles sous la question d'origine. Merci pour toutes les réponses intéressantes! Bien sûr, tout le monde peut continuer à publier de nouvelles découvertes.

Pour quelles familles de graphes existe-t-il un algorithme polynomial de temps pour calculer le nombre chromatique ?$\chi(G)$

Le problème est résoluble en temps polynomial quand (graphes bipartis). En général, quand , le calcul du nombre chromatique est NP-difficile, mais il existe de nombreuses familles de graphes où ce n'est pas le cas. Par exemple, des cycles de coloration et des graphiques parfaits peuvent être effectués en temps polynomial.$\chi(G) = 2$$\chi(G) \ge 3$

De plus, pour de nombreuses classes de graphes, nous pouvons simplement évaluer le polynôme chromatique correspondant; quelques exemples dans Mathworld .

Je suppose que la plupart de ce qui précède est de notoriété publique. Je serais ravi de savoir s'il existe d'autres familles de graphes (non triviales) pour lesquelles la coloration minimale du graphe est résoluble en temps polynomial.

En particulier, je m'intéresse aux algorithmes exacts et déterministes mais n'hésitez pas à signaler tout algorithme randomisé ou algorithme d'approximation intéressant.

Mise à jour (31 août):

Merci à tous d'avoir soumis des réponses intéressantes. Voici un bref résumé des réponses et des références.

Graphiques parfaits et presque parfaits

• Algorithmes géométriques et optimisation combinatoire (1988), Chapitre 9 (Ensembles stables dans les graphiques). Martin Grotschel, Laszlo Lovasz, Alexander Schrijver.

  Le chapitre 9 du livre montre comment résoudre le problème de coloration via le problème de couverture de clique pondérée minimale. Puisqu'ils s'appuient sur la méthode ellipsoïde, ces algorithmes peuvent ne pas être très utiles en pratique. De plus, le chapitre a une belle liste de référence pour différentes classes de graphiques parfaits.

• Combinatorial Optimization (2003), Volume B, Section VI Alexander Schrijver.

  Ce livre comprend trois chapitres consacrés aux graphes parfaits et à leur colorabilité polynomiale dans le temps. Je n'ai jeté qu'un coup d'œil rapide mais l'approche de base semble la même que dans le livre précédent.

• Une caractérisation des graphes b-parfaits (2010). Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek

Graphiques avec largeur d'arbre bornée ou largeur de clique

• Ensemble dominant les couleurs et colorations sur les graphiques à largeur de clique fixe (2001). Daniel Kobler, Udi Rotics

  Les algorithmes nécessitent ici une expression k (une formule algébrique pour construire un graphe avec une largeur de clique bornée) comme paramètre. Pour certains graphiques, cette expression peut être calculée en temps linéaire.

• Yaroslav a souligné dans les méthodes de comptage des colorations dans les graphiques de largeur d'arbre délimités. Voir sa réponse ci-dessous.

Ces deux familles de graphes d'étude où sommets ou arêtes peuvent être ajoutés ou supprimés.$k$

• Complexité paramétrisée de la coloration des sommets (2003). Leizhen Cai.

  La coloration peut être résolue en temps polynomial lors de l'ajout ou de la suppression de bords (pour k fixe ) dans les graphiques fractionnés .$k$$k$

• Problèmes de coloration paramétrés sur les graphes en accords (2006). Dániel Marx.

  Pour les fixes , les graphes d'accords auxquels sont ajoutés k arêtes peuvent être colorés en temps polynomial.$k$$k$

Graphiques ne contenant pas de sous-graphiques particuliers

• Décider la k-colorabilité des graphiques sans P5 en temps polynomial (2010). Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada, Xiao Shu.

• Graphiques sans AT à 3 couleurs en temps polynomial (2010). Juraj Stacho.

Coloration des quadtrees

• Algorithmes de coloration des quadtrees (1999). David Eppstein, Marshall W. Bern, Brad Hutchings.

Comme vous le constatez, tous les graphiques parfaits peuvent être colorés en temps polynomial, mais je pense que la preuve implique des algorithmes ellipsoïdes pour la programmation linéaire (voir le livre de Grötschel, Lovász et Schrijver) plutôt que quelque chose de direct et combinatoire. Il existe de nombreuses classes de graphiques différentes qui sont des sous-classes de graphiques parfaits et qui ont des algorithmes de coloration plus faciles; Les graphiques d'accords, par exemple, peuvent être colorés avec avidité en utilisant un ordre d'élimination parfait.

Tous les graphiques connectés localement (graphiques dans lesquels chaque sommet a un voisinage connecté) peuvent être tricolores en temps polynomial, lorsqu'une coloration existe: il suffit d'étendre le triangle de coloration par triangle.

Les graphiques de degré trois maximum peuvent être colorés en temps polynomial: il est facile de tester s'ils sont bipartis, et sinon ils ne nécessitent que trois couleurs ou ils ont K4 comme composant connecté et nécessitent quatre couleurs (théorème de Brooks).

Les graphes planaires sans triangle peuvent être colorés en temps polynomial, pour la même raison: ils sont tout au plus 3-chromatiques (théorème de Grötzsch).

Les graphiques b-parfaits permettent des cycles induits de 5 (contrairement aux graphiques parfaits), et ont été montrés comme ayant un algorithme de temps polynomial pour la coloration par Hoàng, Maffray et Mechebbek, A caractérization of b-perfect graphs , arXiv: 1004.5306 , 2010.

(Il est dommage que le merveilleux recueil de classes de graphes de l' ISGCI ne couvre que la largeur de clique, l'ensemble indépendant et la domination. Il n'inclut pas d'informations sur la coloration.)

Également pour les graphiques de largeur de clique bornée (qui est plus générale que la largeur d'arbre): Kobler et Rotics .

$n^{f(k)}$

En outre, la largeur de clique est difficile à calculer, mais il existe un algorithme d'approximation par Oum et Seymour, "pproximant la largeur de clique et la largeur de branche" (avec approximation exponentielle).

$k$

Toute famille de graphiques avec une largeur d' arbre bornée aura un algorithme de temps polynomial pour calculer le nombre chromatique. Gamarnik réduit le problème du comptage des colorations à celui du calcul des marginaux de certains champs aléatoires de Markov définis sur le même graphique. Le résultat suit parce que les marginaux des MRF sur les graphiques de largeur d'arbre bornés peuvent être calculés en temps polynomial avec l' algorithme d' arbre de jonction .

Mise à jour 8/26 : Voici un exemple de réduction du nombre de colorants <-> <-> marginaux. Cela nécessite de commencer par une coloration appropriée, qui peut être trouvée en temps polynomial pour les graphiques de largeur d'arbre bornés avec la version max-plus de l'algorithme d'arbre de jonction. Maintenant, à bien y penser ... vous n'avez pas vraiment besoin de # de colorations pour le nombre chromatique, juste une seule coloration appropriée

$P_5$$C_5$$P_5$

$2P_3$

Il y a aussi des résultats de Daniel Marx concernant la complexité du problème des nombres chromatiques sur les graphiques qui peuvent être accordés par au plus k suppressions de sommets; pour chaque k fixe, ce problème est polynomial ( http://dx.doi.org/10.1016/j.tcs.2005.10.008 ).

Algorithmes de coloration des quadruples .
M. Bern, D. Eppstein et B. Hutchings.
http: // arXiv: cs.CG/9907030 .
Algorithmica 32 (1): 87-94, 2002.

Nous considérons plusieurs variantes du problème de la coloration des carrés d'un quadtree de sorte qu'il n'y ait pas deux carrés adjacents qui soient colorés de la même manière. Nous proposons des algorithmes de temps linéaires simples pour les quadruples équilibrés à 3 couleurs avec contiguïté des bords, les quadruples déséquilibrés à 4 couleurs avec contiguïté des bords et les quadruples équilibrés ou non équilibrés à 6 couleurs avec contiguïté des coins. Le nombre de couleurs utilisées par les deux premiers algorithmes est optimal; pour le troisième algorithme, 5 couleurs peuvent parfois être nécessaires.