Geodesic
Study of boundary graph classes for colorability problems
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 6, pp. 37-48

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

The notion of a boundary graph class is a helpfull tool for computational complexity analysis of graph theory problems in the family of hereditary graph classes. Some general and specific features for families of boundary graph classes for the vertex-$k$-colorability problem and its “limited” variant, the chromatic number problem were investigated in previous papers of the author. In this paper, the similar research is conducted for the edge-$k$-colorability and the chromatic index problems. Every boundary class for the edge-$3$-colorability problem is a boundary class for the chromatic index problem. Surprisingly, for any $k>3$ there exist uncountably many boundary classes for the edge-$k$-colorability problem such that each of them is not boundary for the chromatic index problem. Finally, we formulate a necessary condition for existence of boundary graph classes for the vertex-$3$-colorability problem which are not boundary for the chromatic number problem. To the author's mind, the resolution of the condition cannot be true and, hence, there are no such boundary classes for the vertex-$3$-colorability problem. Bibliogr. 11.
Keywords: computational complexity, boundary graph class, colorability problem. 
@article{DA_2012_19_6_a3,
     author = {D. S. Malyshev},
     title = {Study of boundary graph classes for colorability problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {37--48},
     publisher = {mathdoc},
     volume = {19},
     number = {6},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_6_a3/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Study of boundary graph classes for colorability problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 37
EP  - 48
VL  - 19
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_6_a3/
LA  - ru
ID  - DA_2012_19_6_a3
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Study of boundary graph classes for colorability problems
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 37-48
%V 19
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_6_a3/
%G ru
%F DA_2012_19_6_a3
D. S. Malyshev. Study of boundary graph classes for colorability problems. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 6, pp. 37-48. http://geodesic.mathdoc.fr/item/DA_2012_19_6_a3/