Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
From MaRDI portal
Publication:5090168
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
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1979486 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- 4-coloring \(H\)-free graphs when \(H\) is small
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- Coloring edges and vertices of graphs without short or long cycles
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complexity classification of the edge coloring problem for a family of graph classes
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Edge dominating set and colorings on graphs with fixed clique-width
- Four-coloring \(P_6\)-free graphs
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Line graphs of bounded clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- On coloring a class of claw-free graphs.
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- Polynomial cases for the vertex coloring problem
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Polynomial-time approximation algorithms for the coloring problem in some cases
- Structure and algorithms for (cap, even hole)-free graphs
- The NP-Completeness of Edge-Coloring
- The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
- The coloring problem for classes with two small obstructions
- 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
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Two cases of polynomial-time solvability for the coloring problem
- Two complexity results for the vertex coloring problem
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Vertex coloring of graphs with few obstructions
Cited in
(5)- 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?)
- 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)
