Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretnyi Analiz i Issledovanie Operatsii, 2022, Volume 29, Issue 2, Pages 38–61
DOI: https://doi.org/10.33048/daio.2022.29.721
(Mi da1297)
 

This article is cited in 1 scientific paper (total in 1 paper)

Some cases of polynomial solvability for the edge colorability problem generated by forbidden $8$-edge subcubic forests

D. S. Malysheva, O. I. Duginovb

a National Research University “Higher School of Economics”, 25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
b Belarusian State University, 4 Nezavisimost Avenue, 220030 Minsk, Belarus
Full-text PDF (383 kB) Citations (1)
References:
Abstract: The edge-coloring problem, is to minimize the number of colors sufficient to color all the edges of a given graph so that any adjacent edges receive distinct colors. For all the classes defined by sets of forbidden subgraphs with 7 edges each, the complexity status of this problem is known. In this paper, we consider the case of prohibitions with 8 edges. It is not hard to see that the edge-coloring problem is NP-complete for such a class if there are no subcubic forests among its 8-edge prohibitions. We prove that forbidding any subcubic 8-edge forest generates a class with polynomial-time solvability of the edge-coloring problem, except for the cases formed by the disjunctive sum of one of 4 forests and an empty graph. For all the remaining four cases, we prove a similar result for the intersection with the set of graphs of maximum degree at least four. Illustr. 2, bibliogr. 14.
Keywords: monotone class, edge-coloring problem, computational complexity.
Funding agency Grant number
Russian Foundation for Basic Research 20–51–04001
Belarusian Republican Foundation for Fundamental Research Ф21РМ–001
This research is supported by the Russian Foundation for Basic Research and the Belarusian Republic Foundation for Basic Research (Project 20–51–04001 (F21RM–001)).
Received: 07.07.2021
Revised: 04.02.2022
Accepted: 07.02.2022
Bibliographic databases:
Document Type: Article
UDC: 519.17
Language: Russian
Citation: D. S. Malyshev, O. I. Duginov, “Some cases of polynomial solvability for the edge colorability problem generated by forbidden $8$-edge subcubic forests”, Diskretn. Anal. Issled. Oper., 29:2 (2022), 38–61
Citation in format AMSBIB
\Bibitem{MalDug22}
\by D.~S.~Malyshev, O.~I.~Duginov
\paper Some cases of polynomial solvability for~the~edge~colorability problem generated by~forbidden $8$-edge subcubic forests
\jour Diskretn. Anal. Issled. Oper.
\yr 2022
\vol 29
\issue 2
\pages 38--61
\mathnet{http://mi.mathnet.ru/da1297}
\crossref{https://doi.org/10.33048/daio.2022.29.721}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4523642}
Linking options:
  • https://www.mathnet.ru/eng/da1297
  • https://www.mathnet.ru/eng/da/v29/i2/p38
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Statistics & downloads:
    Abstract page:172
    Full-text PDF :28
    References:24
    First page:5
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024