희소 이웃 그래프의 팔레트 희소화
그래프 색칠 문제에서, 최대 차수 Δ인 n-정점 그래프에서 각 정점당 Θ(log n)개의 색을 샘플링하면 적절한 색칠이 가능하다는 기존 연구가 있습니다. 삼각형 없는 그래프의 경우 O(Δ/log Δ) 색칠에 대한 유사한 결과도 도출되었습니다. 이러한 결과는 조합론적 중요성뿐만 아니라 다양한 계산 모델에서 그래프 색칠 알고리즘 설계에 응용됩니다. 본 연구는 국소적으로 희소한 그래프, 즉 희소한 이웃을 가진 그래프에 초점을 맞춥니다. k-국소적으로 희소한 그래프는 각 정점 v의 이웃 G[N(v)]가 최대 k개의 간선을 포함하는 그래프…