Complexity classification of the edge coloring problem for a family of graph classes
type: Item
instance of: scholarly article
title: Complexity classification of the edge coloring problem for a family of graph classes
zbMATH Open document ID: 1373.05068
author: D. S. Malyshev
published in: Discrete Mathematics and Applications
publication date: 2017-11-02T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6802432
zbMATH Keywords: computational complexity
zbMATH Keywords: chromatic index problem
zbMATH Keywords: efficient algorithm
MaRDI profile type: Publication
full work available at URL: dma-2017-0011
OpenAlex ID: W2608830549
cites work: The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
cites work: Q4425939
cites work: Updating the complexity status of coloring graphs without a fixed induced linear forest
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: 4-coloring \(H\)-free graphs when \(H\) is small
cites work: Line graphs of bounded clique-width
cites work: Edge dominating set and colorings on graphs with fixed clique-width
cites work: Q3558598
cites work: The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
cites work: Three-colourability and forbidden subgraphs. II: Polynomial algorithms
cites work: A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
cites work: Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
DOI: 10.1515/DMA-2017-0011
description: scientific article; zbMATH DE number 6802432