Coloring k-colorable graphs using relatively small palettes.
We obtain the following new coloring results: ? A 3-colorable graph on n vertices with maximum degree Δ can be colored, in polynomial time, using O((ΔlogΔ)1/3·logn) colors. This slightly improves an O((Δ1/3log1/2Δ)·logn) bound given by Karger, Motwani, and Sudan. More generally, k-colorable graphs...
| প্রকাশিত: | Journal of algorithms. 45, 1 (2002). |
|---|---|
| প্রধান লেখক: | |
| বিন্যাস: | প্রবন্ধ |
| ভাষা: | English |
| বিষয়গুলি: |