¿Qué se sabe sobre la dureza del índice cromático para las clases de grafos restringidos?

Hay un buen artículo de 1991 que contiene tres diagramas sobre diferentes familias de clases de grafos que muestran lo que se sabe sobre la dureza de determinar el índice cromático para ellos. ¿Hay alguna noticia desde entonces sobre esto?

Estoy más interesado en lo que se sabe sobre gráficos con un número cromático acotado. Mi curiosidad ha sido generada por /mathpro/238448/hypergraph-edge-colouring .

graph-theory np-hardness graph-colouring domotorp
fuente

graphclasses.org tiene una lista por clase de la complejidad de probar si un gráfico es de 3 colores y otro para probar si es k-colorable . También tiene una gran lista de clases para las cuales se limita el número cromático .

Peter Taylor

@ Peter: No pude encontrar el índice cromático en la base de fechas.

domotorp

Respuestas:

Aquí hay un resultado muy relevante:

Koreas, Diamantis P. (1997), "La completitud NP del índice cromático en gráficos libres de triángulos con vértice máximo de grado 3", Appl. Matemáticas. Comput 83 (1): 13-17 .

El título se explica por sí mismo.

David Eppstein
fuente

Si el título se explica por sí mismo, entonces es un resultado bastante trivial. Me refiero al artículo de 1981 de Holyer que mostró que la NP completa del índice cromático dio, de hecho, un gráfico cúbico libre de triángulos. (En un gráfico cúbico, uno puede reemplazar fácilmente cada triángulo por un vértice al estudiar si el índice cromático es 3 o 4.)

domotorp