Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find




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

Diskretnaya Matematika, 2016, Volume 28, Issue 2, Pages 44–50
DOI: https://doi.org/10.4213/dm1367 (Mi dm1367) 		 
This article is cited in 6 scientific papers (total in 6 papers)

Complexity classification of the edge coloring problem for a family of graph classes

D. S. Malyshevab

a State University – Higher School of Economics in Nizhnii Novgorod
b Lobachevski State University of Nizhni Novgorod
Full-text PDF (390 kB) Citations (6)
References:
PDF
HTML
DOI: https://doi.org/10.4213/dm1367
Abstract: A class of graphs is called monotone if it is closed under deletion of vertices and edges. Any such class may be defined in terms of forbidden subgraphs. The chromatic index of a graph is the smallest number of colors required for its edge-coloring such that any two adjacent edges have different colors. We obtain a complete classification of the complexity of the chromatic index problem for all monotone classes defined in terms of forbidden subgraphs having at most 6 edges or at most 7 vertices.
Keywords: computational complexity, chromatic index problem, efficient algorithm.
Funding agency Grant number
Russian Foundation for Basic Research 16-31-60008-мол_а_дк
Ministry of Education and Science of the Russian Federation МК-4819.2016.1
This research was carried out with the financial support of the Russian Foundation for Basic Research (grant no. 16-31-60008-mol_a_dk, the Council on Grants of the President of the Russian Federation (grant no. MK-4819.2016.1), and the LATNA laboratory at the National Research University Higher School of Economics.
Received: 11.01.2016
English version:
Discrete Mathematics and Applications, 2017, Volume 27, Issue 2, Pages 97–101
DOI: https://doi.org/10.1515/dma-2017-0011
Bibliographic databases:
Document Type: Article
UDC: 519.174
Language: Russian
Citation: D. S. Malyshev, “Complexity classification of the edge coloring problem for a family of graph classes”, Diskr. Mat., 28:2 (2016), 44–50; Discrete Math. Appl., 27:2 (2017), 97–101
Citation in format AMSBIB
\Bibitem{Mal16}
\by D.~S.~Malyshev
\paper Complexity classification of the edge coloring problem for a~family of graph classes
\jour Diskr. Mat.
\yr 2016
\vol 28
\issue 2
\pages 44--50
\mathnet{http://mi.mathnet.ru/dm1367}
\crossref{https://doi.org/10.4213/dm1367}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3559790}
\elib{https://elibrary.ru/item.asp?id=26414201}
\transl
\jour Discrete Math. Appl.
\yr 2017
\vol 27
\issue 2
\pages 97--101
\crossref{https://doi.org/10.1515/dma-2017-0011}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000403472300004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85018449158}
Linking options:
  • https://www.mathnet.ru/eng/dm1367
  • https://doi.org/10.4213/dm1367
  • https://www.mathnet.ru/eng/dm/v28/i2/p44
    • This publication is cited in the following 6 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретная математика
    Statistics & downloads:
    Abstract page:401
    Full-text PDF :67
    References:39
    First page:22
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024