Volume 19, No 6, 2012, P. 37-48

UDC 519.178
D. S. Malyshev 
Study of boundary graph classes for colorability problems

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

Malyshev Dmitriy Sergeevich ^1,2
1. Higher school of economics at Nizhniy Novgorod,
25/12 B. Pecherskaya st., 603155 Nizhny Novgorod, Russia
2. Nizhniy Novgorod State University,
23 Gagarin ave., 603950 Nizhniy Novgorod, Russia
e-mail: dsmalyshev@rambler.ru