On the number of boundary classes in the 3-colouring problem
Dmitriy Sergeevich Malyshev · Discrete Mathematics and Applications · 2009
The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for the 3-colouring problem is infinite.