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

DOI10.1515/DMA-2017-0011MaRDI QIDQ1675533zbMATH OpenOpenAlexFDO

Authors D. 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

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

Recommendations

• Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
• Edge-coloring of split graphs.
• Chromatic index of graphs with no cycle with a unique chord
• Edge-coloring of multigraphs
• The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices

Cites work

• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• 4-coloring \(H\)-free graphs when \(H\) is small
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Coloring edges and vertices of graphs without short or long cycles
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Edge dominating set and colorings on graphs with fixed clique-width
• Line graphs of bounded clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• 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
• Updating the complexity status of coloring graphs without a fixed induced linear forest

Cited in

(10)

• The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
• scientific article; zbMATH DE number 7656024 (Why is no real title available?)
• Polynomial time complexity of edge colouring graphs with bounded colour classes
• Edge-coloring of split graphs.
• Chromatic index of graphs with no cycle with a unique chord
• Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
• A study of the boundary graph classes for colorability problems
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• Complexity-separating graph classes for vertex, edge and total colouring
• Classifying \(k\)-edge colouring for \(H\)-free graphs

This page was built for publication: Complexity classification of the edge coloring problem for a family of graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1675533)