Что известно о твердости хроматического индекса для классов ограниченных графов?

Есть хорошая статья 1991 года, которая содержит три диаграммы о различных семействах графов, показывающих то, что известно о сложности определения хроматического индекса для них. Есть ли какие-либо новости с тех пор?

Меня больше всего интересует то, что известно о графах с ограниченным хроматическим числом. Мое любопытство было поднято /mathpro/238448/hypergraph-edge-colouring .

graph-theory np-hardness graph-colouring domotorp
источник

У graphclasses.org есть список по классам сложности тестирования, является ли граф 3-цветным, а другой - для проверки, является ли он k-окрашенным . Он также имеет большой список классов, для которых хроматическое число ограничено .

Питер Тейлор

@Peter: я не мог найти хроматический индекс в базе данных.

domotorp

Ответы:

Вот один очень важный результат:

Koreas, Diamantis P. (1997), "NP-полнота хроматического индекса в графах без треугольников с максимальной вершиной степени 3", Appl. Математика Вычи. 83 (1): 13–17 .

Название говорит само за себя.

Дэвид Эппштейн
источник

Если заголовок говорит само за себя, то это довольно тривиальный результат. Я имею в виду, что статья Холиера 1981 года, в которой была показана NP-полнота хроматического индекса, фактически дала кубический граф без треугольников. (В кубическом графе каждый треугольник можно легко заменить вершиной при изучении того, равен ли хроматический индекс 3 или 4.)

domotorp