Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem

DOI10.33048/daio.2020.27.682zbMath1493.05107OpenAlexW4235200509MaRDI QIDQ5090168

Dmitriy 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

zbMATH Keywords

computational complexityedge coloring problemstrongly hereditary class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex coloring of graphs with few obstructions
• The coloring problem for classes with two small obstructions
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Two complexity results for the vertex coloring problem
• Polynomial cases for the vertex coloring problem
• 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
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• Complexity classification of the edge coloring problem for a family of graph classes
• Structure and algorithms for (cap, even hole)-free graphs
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• 4-coloring \(H\)-free graphs when \(H\) is small
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edge dominating set and colorings on graphs with fixed clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• On coloring a class of claw-free graphs.
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Polynomial-time approximation algorithms for the coloring problem in some cases
• 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
• Line graphs of bounded clique-width
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• The NP-Completeness of Edge-Coloring
• On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
• The class of (P7,C4,C5)‐free graphs: Decomposition, algorithms, and χ‐boundedness
• Four-coloring P₆-free graphs
• Two cases of polynomial-time solvability for the coloring problem

This page was built for publication: Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem