У теорії графівповне розфарбування — це протилежність гармонійному розфарбуванню в тому сенсі, що це розфарбування вершин, у якому кожна пара кольорів зустрічається принаймні на одній парі суміжних вершин. Еквівалентно, повне розфарбування — це мінімальне розфарбування, в тому сенсі, що його не можна перетворити на правильне розфарбування з меншим числом кольорів злиттям двох кольорів. Ахроматичне число графа — це найбільше число кольорів серед усіх повних розфарбувань графа .
Питання: Чи існує розбиття множини вершин на або більше неперетинних множин таких, що кожне є незалежною множиною для і таких, що для кожної пари різних множин незалежною множиною не є.
Визначення ахроматичного числа є NP-складною задачею. Визначення, чи не буде ахроматичне число більшим від заданого числа є NP-повною задачею, як показали Янакакіс і Гаврил (Yannakakis, Gavril) 1978 року, перетворивши з задачі пошуку мінімального найбільшого парування[1].
Зауважимо, що будь-яке розфарбування графа з найменшим числом кольорів має бути повним розфарбуванням, так що мінімізація числа кольорів повного розфарбування є просто переформулюванням стандартної задачі розфарбовування графа.
↑ абAmitabh Chaudhary, Sundar Vishwanathan. Approximation algorithms for the achromatic number // Journal of Algorithms. — 2001. — Т. 41, вип. 2. — С. 404—416. — DOI:10.1006/jagm.2001.1192..
↑M. Farber, G. Hahn, P. Hell, D. J. Miller. Concerning the achromatic number of graphs // Journal of Combinatorial Theory, Series B. — 1986. — Т. 40, вип. 1. — С. 21—39. — DOI:10.1016/0095-8956(86)90062-6..
↑H. Bodlaender. Achromatic number is NP-complete for cographs and interval graphs // Inform. Proc. Lett.. — 1989. — Т. 31, вип. 3. — С. 135—138. — DOI:10.1016/0020-0190(89)90221-4..
↑D. Manlove, C. McDiarmid. The complexity of harmonious coloring for trees // Discrete Applied Mathematics. — 1995. — Т. 57, вип. 2-3. — С. 133—144. — DOI:10.1016/0166-218X(94)00100-R..
↑M. Yannakakis, F. Gavril. Edge dominating sets in graphs // SIAM Journal on Applied Mathematics. — 1980. — Т. 38, вип. 3. — С. 364—372. — DOI:10.1137/0138030..
↑Y. Roichman. On the Achromatic Number of Hypercubes // Journal of Combinatorial Theory, Series B. — 2000. — Т. 79, вип. 2. — С. 177—182. — DOI:10.1006/jctb.2000.1955..