O que se sabe sobre a dureza do índice cromático para classes de gráfico restritas?

9

Há um belo artigo de 1991 que contém três diagramas sobre famílias de classes gráficas diferentes, mostrando o que se sabe sobre a dureza de determinar o índice cromático para eles. Desde então, há alguma notícia sobre isso?

Estou mais interessado no que se sabe sobre gráficos com um número cromático limitado. Minha curiosidade foi despertada por /mathpro/238448/hypergraph-edge-colouring .

graph-theory np-hardness graph-colouring domotorp
fonte
graphclasses.org tem uma lista por classe da complexidade de testar se um gráfico é de três cores e outra para testar se é um k-colorido . Ele também possui uma grande lista de classes para as quais o número cromático é limitado .
27568 Peter Pan em
@ Peter: Não consegui encontrar o índice cromático no banco de dados.
Domotorp 7/08

Respostas:

2

Aqui está um resultado muito relevante:

Koreas, Diamantis P. (1997), "A NP-completude do índice cromático em gráficos livres de triângulo com vértice máximo de grau 3", Appl. Matemática. Comput. 83 (1): 13-17 .

O título é auto-explicativo.

David Eppstein
fonte
5
Se o título é auto-explicativo, é um resultado bastante trivial. Quero dizer, o artigo de 1981 de Holyer, que mostrou a completude de NP do índice cromático, deu de fato um gráfico cúbico sem triângulo. (Em um gráfico cúbico, uma pode facilmente substituir cada triângulo por um vértice quando a estudar se o índice cromático é 3 ou 4.)
domotorp