This article is cited in 5 scientific papers (total in 5 papers)
Study of boundary graph classes for colorability problems
D. S. Malyshevab
a Higher school of economics at Nizhniy Novgorod, Nizhny Novgorod, Russia
b Nizhniy Novgorod State University, Nizhniy Novgorod, Russia
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.
computational complexity, boundary graph class, colorability problem.
PDF file (277 kB)
Journal of Applied and Industrial Mathematics, 2013, 7:2, 221–228
D. S. Malyshev, “Study of boundary graph classes for colorability problems”, Diskretn. Anal. Issled. Oper., 19:6 (2012), 37–48; J. Appl. Industr. Math., 7:2 (2013), 221–228
Citation in format AMSBIB
\paper Study of boundary graph classes for colorability problems
\jour Diskretn. Anal. Issled. Oper.
\jour J. Appl. Industr. Math.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
D. S. Malyshev, “Extending operators for the independent set problem”, J. Appl. Industr. Math., 7:3 (2013), 412–419
D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Sib. elektron. matem. izv., 11 (2014), 811–822
Malyshev D.S., “the Coloring Problem For Classes With Two Small Obstructions”, Optim. Lett., 8:8 (2014), 2261–2270
D. S. Malyshev, O. O. Lobanova, “Two complexity results for the vertex coloring problem”, Discrete Appl. Math., 219 (2017), 158–166
V. V. Lozin, D. S. Malyshev, “Vertex coloring of graphs with few obstructions”, Discrete Appl. Math., 216:1, SI (2017), 273–280
|Number of views:|