RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2016 Volume 28, Issue 2, Pages 44–50 (Mi dm1367)

This article is cited 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

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.

UDC: 519.174

Received: 11.01.2016

DOI: 10.4213/dm1367


 English version:
Discrete Mathematics and Applications, 2017, 27:2, 97–101

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024