• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

A Study of the Boundary Graph Classes for Colorability Problems

Journal of Applied and Industrial Mathematics. 2013. Vol. 7. No. 2. P. 221-228.

The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by the author earlier. In the present article, these problems are considered in application to the edge version of the colorability problem. It turns out that each boundary class for the edge 3-colorability problem is a boundary class for the chromatic index problem; however, for each k > 3, there exist uncountably many boundary classes for the edge k-colorability problem each of which is not a boundary class for the chromatic index problem.We formulate some necessary condition for the existence of boundary classes of graphs for the vertex 3-colorability problem which are not boundary for the chromatic index problem. To the author’s mind, this condition is never satis.ed and so there are no such boundary classes for the vertex 3-colorability problem.