Que sait-on de la dureté de l'indice chromatique pour les classes de graphes restreintes?

9

Il y a un beau papier de 1991 qui contient trois diagrammes sur différentes familles de classes de graphes montrant ce que l'on sait de la dureté de la détermination de l'indice chromatique pour eux. Y a-t-il depuis des nouvelles à ce sujet?

Ce qui m'intéresse le plus, ce sont les graphiques avec un nombre chromatique borné. Ma curiosité a été soulevée par /mathpro/238448/hypergraph-edge-colouring .

graph-theory np-hardness graph-colouring domotorp
la source
graphclasses.org a une liste par classe de la complexité de tester si un graphique est à 3 couleurs et un autre pour tester s'il est à k couleurs . Il a également une grande liste de classes pour lesquelles le nombre chromatique est borné .
Peter Taylor
@Peter: Je n'ai pas trouvé d'index chromatique dans la base de données.
domotorp

Réponses:

2

Voici un résultat très pertinent:

Koreas, Diamantis P. (1997), "L'exhaustivité NP de l'indice chromatique dans les graphes sans triangle avec un sommet maximal de degré 3", Appl. Math. Comput. 83 (1): 13-17 .

Le titre est explicite.

David Eppstein
la source
5
Si le titre est explicite, c'est un résultat assez trivial. Je veux dire l'article de Holyer de 1981 qui montrait que NP-complétude de l'indice chromatique donnait en fait un graphique cubique sans triangle. (Dans un graphique cubique, on peut facilement remplacer chaque triangle par un sommet lorsque l'on étudie si l'indice chromatique est 3 ou 4.)
domotorp