آره مساله Vertex coloring از نظر زمان اجرا جزو مسایل NP_Complete هستش .
منظور سوال تقریب زدن هم نیست چون تقریب تعریف دقیقی نداره هر تابعی که جواب درست بده ولی لزوما کمترین تعداد مورد نیاز نباشه میشه در نظر گرفت مثلا من با (1)O میام گراف رو می گیرم بعد تعداد راس ها رو بر می گردونم :)
شاید هم مظور از نظر ریاضیاتی بوده نه زمان محاسباتی یعنی این که در بدترین حالت چند تا رنگ نیاز داریم (که خب باز هم رادیکال n درست نیست چون مثلا برای گراف کامل n راسی n تا رنگ هم نیاز داریم )
این سوال از کدوم کتابه ؟ :)