Co wiadomo na temat twardości wskaźnika chromatycznego dla ograniczonych klas grafów?

9

Jest ładny papier z 1991 roku, który zawiera trzy diagramy dotyczące różnych rodzin klas grafów, pokazujące, co wiadomo na temat twardości wyznaczania dla nich indeksu chromatycznego. Czy są odtąd jakieś wiadomości na ten temat?

Najbardziej interesuje mnie to, co wiadomo na temat wykresów z ograniczoną liczbą chromatyczną. Moja ciekawość została podniesiona przez /mathpro/238448/hypergraph-edge-colouring .

graph-theory np-hardness graph-colouring domotorp
źródło
graphclasses.org ma listę według klasy złożoności testowania, czy wykres jest trójkolorowy, a drugą do testowania, czy jest on koloryzujący . Ma także dużą listę klas, dla których liczba chromatyczna jest ograniczona .
Peter Taylor,
@Peter: Nie mogłem znaleźć indeksu chromatycznego w bazie danych.
domotorp

Odpowiedzi:

2

Oto jeden bardzo trafny wynik:

Koreas, Diamantis P. (1997), „Kompletność NP wskaźnika chromatycznego w grafach bez trójkątów z maksymalnym wierzchołkiem stopnia 3”, Appl. Matematyka Comput. 83 (1): 13–17 .

Tytuł jest oczywisty.

David Eppstein
źródło
5
Jeśli tytuł jest oczywisty, to wynik jest dość trywialny. Mam na myśli papier Holyera z 1981 r., Który wykazał kompletność NP wskaźnika chromatycznego, w rzeczywistości przedstawił wykres sześcienny bez trójkąta. (Na wykresie sześciennym można łatwo zastąpić każdy trójkąt wierzchołkiem, badając, czy indeks chromatyczny wynosi 3, czy 4.)
domotorp