Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
DOI10.33048/DAIO.2020.27.682zbMATH Open1493.05107OpenAlexW4235200509MaRDI QIDQ5090168FDOQ5090168
Authors: D. S. Malyshev 
Publication date: 15 July 2022
Published in: Diskretnyi analiz i issledovanie operatsii (Search for Journal in Brave)
Full work available at URL: http://mathnet.ru/eng/da1269
Recommendations
- Complexity classification of the edge coloring problem for a family of graph classes
- 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
- Coloring graphs characterized by a forbidden subgraph
- Coloring graphs characterized by a forbidden subgraph
Analysis of algorithms and problem complexity (68Q25) 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
- Title not available (Why is that?)
- 4-coloring \(H\)-free graphs when \(H\) is small
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- 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
- Vertex coloring of graphs with few obstructions
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- The coloring problem for classes with two small obstructions
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
- Coloring edges and vertices of graphs without short or long cycles
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Edge dominating set and colorings on graphs with fixed clique-width
- Line graphs of bounded clique-width
- Title not available (Why is that?)
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Two complexity results for the vertex coloring problem
- Two cases of polynomial-time solvability for the coloring problem
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Polynomial cases for the vertex coloring problem
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- Four-coloring \(P_6\)-free graphs
- Structure and algorithms for (cap, even hole)-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- On coloring a class of claw-free graphs.
- Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
- Polynomial-time approximation algorithms for the coloring problem in some cases
- Complexity classification of the edge coloring problem for a family of graph classes
Cited In (5)
- 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
- Complexity classification of the edge coloring problem for a family of graph classes
- 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
This page was built for publication: Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090168)
