Pedido de Referência: dureza assintótico de

10

Ouvi falar de um resultado na coloração aproximada do gráfico, mas não consigo encontrar a fonte. O resultado é:

Para cada constante existe uma suficientemente grande k tal que a coloração de um k gráfico -colorable com h k cores é NP-duro.hkkhk

Alguém poderia me indicar o jornal relevante?

Jeremy Kun
fonte

Respostas:

11

Existem resultados muito mais fortes para a coloração aproximada do gráfico.

Igor Shinkar
fonte
O último resultado é interessante, mas há um problema de ponto decimal aí? Dois zeros antes do decimal são ímpares ...
Jeremy Kun