새로운 근사 그래프 색칠 알고리즘

A를 그래프 색칠 알고리즘이라고 하자. A가 그래프 G를 색칠하는 데 사용하는 최대 색상의 수와 G의 크로마틱 넘버 x(G) 사이의 비율을 À(G)라고 하자. 대부분의 기존 다항식 색칠 알고리즘의 경우, À(G)는 O(n)만큼 나쁠 수 있으며, 여기서 n은 G의 정점 수이다. 현재 알려진 가장 좋은 알고리즘은 À(G)=O(n/logn)을 보장한다. 본 논문에서는 À(G)≤x(G)n (방정식)을 보장하는 간단하고 효율적인 색칠 알고리즘을 제시하며, 현재의 경계를 상당히 개선한 것이다.