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

DOI10.1515/dma-2017-0011zbMath1373.05068OpenAlexW2608830549MaRDI QIDQ1675533

Dmitriy S. Malyshev

Publication date: 2 November 2017

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma-2017-0011

zbMATH Keywords

computational complexityefficient algorithmchromatic index problem

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Unnamed Item ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• 4-coloring \(H\)-free graphs when \(H\) is small
• Edge dominating set and colorings on graphs with fixed clique-width
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Linear time solvable optimization problems on graphs of bounded clique-width
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Line graphs of bounded clique-width