Geodesic
On the number of boundary classes in the 3-colouring problem
Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 129-134.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2009_21_4_a10,
     author = {D. S. Malyshev},
     title = {On the number of boundary classes in the 3-colouring problem},
     journal = {Diskretnaya Matematika},
     pages = {129--134},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_4_a10/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - On the number of boundary classes in the 3-colouring problem
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 129
EP  - 134
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_4_a10/
LA  - ru
ID  - DM_2009_21_4_a10
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T On the number of boundary classes in the 3-colouring problem
%J Diskretnaya Matematika
%D 2009
%P 129-134
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2009_21_4_a10/
%G ru
%F DM_2009_21_4_a10
D. S. Malyshev. On the number of boundary classes in the 3-colouring problem. Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 129-134. http://geodesic.mathdoc.fr/item/DM_2009_21_4_a10/

[1] Stockmeyer L., “Planar 3-colourability is polynomial complete”, ACM SIGACT News, 5:3 (1973), 19–25 | DOI

[2] Kochol M., Lozin V., Randerath B., “The 3-colourability problem on graphs with maximum degree four”, SIAM J. Comput., 32:5 (2003), 1128–1139 | DOI | MR | Zbl

[3] Grötchel M., Lovász L., Schrijver A., “The ellipsoid method and its consequences in combinatorial optimization”, Combinatorica, 1:2 (1981), 169–197 | DOI | MR

[4] Alekseev V. E., “On easy and hard hereditary classes of graphs with respect to the independent set problem”, Discrete Appl. Math., 132:1–3 (2004), 17–26 | DOI | MR

[5] Alekseev V. E., “A polynomial algorithm for finding largest independent sets in fork-free graphs”, Discrete Appl. Math., 135:1–3 (2004), 3–16 | MR

[6] Malyshev D. S., “Granichnye klassy dlya zadachi o nezavisimom mnozhestve v klasse planarnykh grafov”, Vestnik Nizhegorodskogo gosudarstvennogo univ. im. N. I. Lobachevskogo, 2007, no. 2, 165–169

[7] Alekseev V. E., Korobitsyn D. V., Lozin V. V., “Boundary classes of graphs for the dominating set problem”, Discrete Math., 285:1–3 (2004), 1–6 | DOI | MR | Zbl