Standard tabu search methods are based on the complete exploration of current solution neighborhood. However, for some problems with very large neighborhood or time-consuming evaluation, the total exploration of the neighborhood is impractical. In this paper, we present an adaptive exploration of neighborhood using extension and restriction mechanisms represented by a loop detection mechanism and a tabu list structure. This approach is applied to the K-coloring problem and evaluated on standard benchmarks like DIMACS in comparison with more powerful recently published algorithms.