Volume 19, No 6, 2012, P. 3748
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 vertexkcolorability 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 edgekcolorability and the chromatic index problems. Every boundary class for the edge3colorability problem is a boundary class for the chromatic index problem. Surprisingly, for any k > 3 there exist uncountably many boundary classes for the edgekcolorability 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 vertex3colorability 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 vertex3colorability 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
email: dsmalyshev@rambler.ru
