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

scientific article; zbMATH DE number 7558128

Language	Label	Description	Also known as
English	Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem	scientific article; zbMATH DE number 7558128

Statements

instance of

scholarly article

0 references

title

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

0 references

zbMATH Open document ID

1493.05107

0 references

DOI

10.33048/daio.2020.27.682

0 references

published in

Diskretnyi analiz i issledovanie operatsii

0 references

publication date

15 July 2022

0 references

full work available at URL

http://mathnet.ru/eng/da1269

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

edge coloring problem

0 references

strongly hereditary class

0 references

computational complexity

0 references

author

Dmitriy S. Malyshev

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

0 references

The NP-Completeness of Edge-Coloring

0 references

Q4448764

0 references

Vertex coloring of graphs with few obstructions

0 references

Polynomial-time algorithms for minimum weighted colorings of $(P_5, \overline{P}_5)$-free graphs and similar graph classes

0 references

Polynomial cases for the vertex coloring problem

0 references

The coloring problem for classes with two small obstructions

0 references

Two cases of polynomial-time solvability for the coloring problem

0 references

The weighted coloring problem for two graph classes characterized by small forbidden induced structures

0 references

Two complexity results for the vertex coloring problem

0 references

Polynomial-time approximation algorithms for the coloring problem in some cases

0 references

The class of (P7,C4,C5)‐free graphs: Decomposition, algorithms, and χ‐boundedness

0 references

Structure and algorithms for (cap, even hole)-free graphs

0 references

On coloring a class of claw-free graphs.

0 references

Characterizations of $(4 K_1,C_4,C_5)$-free graphs

0 references

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs

0 references

Updating the complexity status of coloring graphs without a fixed induced linear forest

0 references

4-coloring $H$-free graphs when $H$ is small

0 references

Three-coloring and list three-coloring of graphs without induced paths on seven vertices

0 references

Four-coloring <i>P</i><sub>6</sub>-free graphs

0 references

Deciding $k$-colorability of $P_5$-free graphs in polynomial time

0 references

Improved complexity results on $k$-coloring $P_t$-free graphs

0 references

The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs

0 references

The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs

0 references

On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size

0 references

Classifying $k$-edge colouring for $H$-free graphs

0 references

The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices

0 references

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

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

Linear time solvable optimization problems on graphs of bounded clique-width

0 references

Q4425939

0 references

Line graphs of bounded clique-width

0 references

Edge dominating set and colorings on graphs with fixed clique-width

0 references

Q3558598

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5090168