✦ LIBER ✦

On the Hardness of Approximating the Chromatic Number

✍ Scribed by Khanna, Sanjeev (author);Linial, Nathan (author);Safra, Shmuel (author)

Publisher: Janos Bolyai Mathematical Society
Year: 2000
Tongue: English
Weight: 311 KB
Volume: 20
Category: Article
ISSN: 0209-9683
DOI: 10.1007/s004930070013

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the Hardness of Approximating the Chr

On the Hardness of Approximating the Chromatic Number

✍ Khanna, Sanjeev (author);Linial, Nathan (author);Safra, Shmuel (author) 📂 Article 📅 2000 🏛 Janos Bolyai Mathematical Society 🌐 English ⚖ 311 KB

Approximating the chromatic index of mul

Approximating the chromatic index of multigraphs

✍ Guantao Chen; Xingxing Yu; Wenan Zang 📂 Article 📅 2009 🏛 Springer US 🌐 English ⚖ 654 KB

On the Hardness of Approximating the Min

On the Hardness of Approximating the Min-Hack Problem

✍ Ramkumar Chinchani; Duc Ha; Anusha Iyer; Hung Q. Ngo; Shambhu Upadhyaya 📂 Article 📅 2005 🏛 Springer US 🌐 English ⚖ 749 KB

On the mean chromatic number

✍ Martin Anthony 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 209 KB

The mean chromatic number of a graph is a measure of the expected performance of the greedy vertex-colouring algorithm when each ordering of the vertices is equally likely. Some results on the value of the mean chromatic number and its asymptotic behaviour are presented.

The Hardness of Approximating Spanner Pr

The Hardness of Approximating Spanner Problems

✍ Michael Elkin; David Peleg 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 366 KB

On the chromatic number of ℝ9

✍ A. B. Kupavskii; A. M. Raigorodskii 📂 Article 📅 2009 🏛 Springer US 🌐 English ⚖ 165 KB