Achromatic number ψ(G): maximum colors in a complete proper coloring (every two color classes joined by at least one edge). χ(G) ≤ ψ(G). Upper bound: ψ ≤ ⌊(1+√(1+2|E|))/2⌋. For K_n: ψ=n. For trees: ψ = ⌊(1+√(1+4(n-1)))/2⌋.
How to Use
Select graph:
- ψ: Achromatic #
- Complete: All pairs used
- Bounds: χ ≤ ψ ≤ √(2|E|)
Duality with χ
χ = minimum proper coloring. ψ = maximum complete coloring. Same type of coloring (proper), opposite optimization direction. The gap ψ-χ measures 'coloring flexibility'. For perfect graphs: ψ can still exceed χ.
Computing ψ
NP-hard in general (Yannakakis-Gavril, 1980). For trees: polynomial O(n²). For complete graphs: trivial. For bipartite graphs: NP-hard even for trees restricted to specific structural conditions.
Step-by-Step Instructions
- 1Select graph.
- 2Compute ψ(G).
- 3Find complete coloring.
- 4Check all pairs.
- 5Compare to χ.