Dureza del número cromático fraccionario aproximado en gráficos de grados acotados

¿Es difícil apx aproximar el número cromático fraccionario en gráficos de grados acotados?

Si.

Si entendí correctamente, la prueba del Teorema 1.6 en Khot (2001) establece que es NP-difícil distinguir entre los siguientes dos casos, incluso si nos centramos en gráficos de grado acotado de grado suficientemente alto:

1. Hay una coloración .$k$
2. La relación entre el número de vértices y el tamaño máximo de un conjunto independiente es al menos .$k^{\log(k)/25}$

Desde la perspectiva del número cromático fraccional, estos dos casos son:

1. El número cromático fraccional es como máximo .$k$
2. El número cromático fraccional es al menos .$k^{\log(k)/25}$

Ahora debemos recordar que necesitamos grados suficientemente altos (en función de ). Pero hasta donde puedo ver, la prueba tiene, por ejemplo, el siguiente corolario conveniente que podría ser suficiente para sus propósitos:$k$

• Dado cualquier constante , no son constantes y de tal manera que el siguiente problema en NP-duro: dada una gráfica de grado máximo , debe decidir si el número cromática fraccionada de es como máximo o al menos .$\alpha$$\Delta$$c$$G$$\Delta$$G$$c$$\alpha c$

Por supuesto, esto ya implica que no hay PTAS, a menos que P = NP.