Diskretnyi Analiz i Issledovanie Operatsii
General information
Latest issue
Impact factor
Guidelines for authors

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

Diskretn. Anal. Issled. Oper., 2012, Volume 19, Issue 6, Pages 37–48 (Mi da710)  

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

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.

Full text: PDF file (277 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2013, 7:2, 221–228

Bibliographic databases:

UDC: 519.178
Received: 29.12.2011
Revised: 24.03.2012

Citation: 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
\by D.~S.~Malyshev
\paper Study of boundary graph classes for colorability problems
\jour Diskretn. Anal. Issled. Oper.
\yr 2012
\vol 19
\issue 6
\pages 37--48
\jour J. Appl. Industr. Math.
\yr 2013
\vol 7
\issue 2
\pages 221--228

Linking options:
  • http://mi.mathnet.ru/eng/da710
  • http://mi.mathnet.ru/eng/da/v19/i6/p37

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. D. S. Malyshev, “Extending operators for the independent set problem”, J. Appl. Industr. Math., 7:3 (2013), 412–419  mathnet  crossref  mathscinet
    2. 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  mathnet
    3. Malyshev D.S., “the Coloring Problem For Classes With Two Small Obstructions”, Optim. Lett., 8:8 (2014), 2261–2270  crossref  mathscinet  zmath  isi  elib  scopus
    4. D. S. Malyshev, O. O. Lobanova, “Two complexity results for the vertex coloring problem”, Discrete Appl. Math., 219 (2017), 158–166  crossref  mathscinet  zmath  isi  scopus
    5. V. V. Lozin, D. S. Malyshev, “Vertex coloring of graphs with few obstructions”, Discrete Appl. Math., 216:1, SI (2017), 273–280  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:314
    Full text:72
    First page:3

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022