关于图顶点涂色的问题

如果有一个函数可以在时间T内决定一个图能否被k种颜色涂色（相同颜色不相邻），能否在O(Tn^2)内将该图涂色，如果可以的话麻烦简单写下思路