RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2009 Volume 21, Issue 4, Pages 129–134 (Mi dm1077)

This article is cited in 4 papers

On the number of boundary classes in the 3-colouring problem

D. S. Malyshev


Abstract: 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.

UDC: 519.7

Received: 08.01.2008

DOI: 10.4213/dm1077


 English version:
Discrete Mathematics and Applications, 2009, 19:6, 625–630

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024