k-컬러링, 채색수 계산보다 빠르다

k-Coloring is Faster than Computing the Chromatic Number

n-정점 그래프에서 k-컬러링 문제를 (2−ε_k)^n 시간에 해결하는 무작위 알고리즘을 제시했다. 여기서 ε_k는 모든 고정 k에 대해 양수이다. 이전에는 k≤6인 경우에만 일반적인 O*(2^n) 알고리즘보다 빠른 해법이 알려져 있었다. 이 연구는 Zamir의 (k+2)-컬러링에서 k-리스트-컬러링으로의 축소와 하이퍼그래프 컨테이너 기법을 결합하고, 길고 짧은 색상 목록이 혼합된 리스트-컬러링 인스턴스를 위한 새로운 알고리즘을 개발하여, 고정 팔레트에서 (k+1)-리스트-컬러링을 k-리스트-컬러링으로 반복적으로 축소하는 방법을 확립했다.