희소 이웃 그래프의 팔레트 희소화

그래프 색칠 문제에서, 최대 차수 Δ인 n-정점 그래프에서 각 정점당 Θ(log n)개의 색을 샘플링하면 적절한 색칠이 가능하다는 기존 연구가 있습니다. 삼각형 없는 그래프의 경우 O(Δ/log Δ) 색칠에 대한 유사한 결과도 도출되었습니다. 이러한 결과는 조합론적 중요성뿐만 아니라 다양한 계산 모델에서 그래프 색칠 알고리즘 설계에 응용됩니다. 본 연구는 국소적으로 희소한 그래프, 즉 희소한 이웃을 가진 그래프에 초점을 맞춥니다. k-국소적으로 희소한 그래프는 각 정점 v의 이웃 G[N(v)]가 최대 k개의 간선을 포함하는 그래프로 정의됩니다. 기존 연구에 따르면 이러한 그래프는 O(Δ/√(k)) 색칠이 가능합니다. 본 연구에서는 임의의 α ∈ (0, 1) 및 k ≪ Δ^(2α)에 대해, k-국소적으로 희소한 그래프 G에서 각 정점당 O(Δ^α + √log n)개의 색을 샘플링하면 적절한 q-색칠(q = Θ(Δ/log(Δ^α/√k)))을 얻기에 충분함을 보입니다. 특히 k=1로 설정하면 삼각형 없는 그래프에 대한 기존 결과가 재현됩니다. 이 결과는 대응 색칠(correspondence coloring)이라는 더 일반적인 설정에서 확립되었으며, 이는 최근 많은 관심을 받고 있는 개념입니다. 증명의 핵심 요소는 G가 적절한 H-색칠을 허용하기 위한 대응 커버 H의 충분 조건을 결정하는 명제입니다. 이 결과는 최근 연구를 개선하며 독립적인 학술적 가치를 지닙니다.