Complexity classification of the edge coloring problem for a family of graph classes
DOI10.1515/DMA-2017-0011zbMATH Open1373.05068OpenAlexW2608830549MaRDI QIDQ1675533FDOQ1675533
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
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
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)
Cites Work
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- 4-coloring \(H\)-free graphs when \(H\) is small
- 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
- 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
- Coloring edges and vertices of graphs without short or long cycles
- Edge dominating set and colorings on graphs with fixed clique-width
- Line graphs of bounded clique-width
- Title not available (Why is that?)
Cited In (10)
- Title not available (Why is that?)
- The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
- 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)
