Was ist über die Härte des chromatischen Index für eingeschränkte Graphklassen bekannt?

Es gibt ein schönes Papier aus dem Jahr 1991, das drei Diagramme über verschiedene Graphklassenfamilien enthält, die zeigen, was über die Härte der Bestimmung des chromatischen Index für sie bekannt ist. Gibt es seitdem Neuigkeiten dazu?

Ich interessiere mich am meisten für das, was über Graphen mit einer begrenzten chromatischen Zahl bekannt ist. Meine Neugier wurde durch /mathpro/238448/hypergraph-edge-colouring geweckt .

graph-theory np-hardness graph-colouring domotorp
quelle

graphclasses.org enthält eine Liste nach Klassen der Komplexität des Testens, ob ein Diagramm dreifarbig ist, und eine andere zum Testen, ob es k-farbig ist . Es gibt auch eine große Liste von Klassen, für die die chromatische Zahl begrenzt ist .

Peter Taylor

@ Peter: Ich konnte keinen chromatischen Index in der Datumsbasis finden.

Domotorp

Antworten:

Hier ist ein sehr relevant aussehendes Ergebnis:

Koreas, Diamantis P. (1997), "Die NP-Vollständigkeit des chromatischen Index in dreieckfreien Graphen mit maximalem Scheitelpunkt 3. Grades", Appl. Mathematik. Comput. 83 (1): 13–17 .

Der Titel ist selbsterklärend.

David Eppstein
quelle

Wenn der Titel selbsterklärend ist, ist es ein ziemlich triviales Ergebnis. Ich meine, die Arbeit von Holyer aus dem Jahr 1981, die die NP-Vollständigkeit des chromatischen Index zeigte, ergab tatsächlich einen dreieckfreien kubischen Graphen. (In einem kubischen Graphen kann man jedes Dreieck leicht durch einen Scheitelpunkt ersetzen, wenn man untersucht, ob der chromatische Index 3 oder 4 ist.)

domotorp