The consistent labeling problem -- which asks whether a given local conjunctive predicate has solutions -- arises in many areas of computer science and particularly in structural pattern/image recognition. Even though the problem is known to be NP-complete in general, there is a strong demand to find subclasses solvable in polynomial time. Research done in this field during the last decade fully clarified the question how complexity of appropriate algorithms solving the problem depends on the complexity of the underlying graph. On the other hand the long history of the problem lacks attempts to find relevant solvable subclasses of the problem by restricting the class of predicates used. In our talk we present a class of predicates and show that consistent labeling can be solved for these in polynomial time even if the underlying graph is fully connected.