A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs (Q6644082)

scientific article; zbMATH DE number 7949962

Language	Label	Description	Also known as
English	A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs	scientific article; zbMATH DE number 7949962

Statements

instance of

scholarly article

0 references

title

A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs (English)

0 references

0 references

0 references

Diskretnyĭ Analiz i Issledovanie Operatsiĭ

0 references

publication date

27 November 2024

0 references

zbMATH Keywords

edge-coloring problem

0 references

computational complexity

0 references

monotone class

0 references

MaRDI profile type

Publication

0 references

cites work

The NP-Completeness of Edge-Coloring

0 references

On an estimate of the chromatic class of a \(p\)-graph

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

Colouring graphs of bounded diameter in the absence of small cycles

0 references

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

0 references

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

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

4-coloring \(H\)-free graphs when \(H\) is small

0 references

Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time

0 references

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

0 references

Improved complexity results on \(k\)-coloring \(P_t\)-free graphs

0 references

Polynomial cases for the vertex coloring problem

0 references

Colouring \((P_r + P_s)\)-free graphs

0 references

Q4448764

0 references

Vertex coloring of graphs with few obstructions

0 references

The coloring problem for classes with two small obstructions

0 references

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

0 references

Two cases of polynomial-time solvability for the coloring problem

0 references

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

0 references

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

0 references

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

0 references

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable

0 references

Two complexity results for the vertex coloring problem

0 references

An intractability result for the vertex 3-colourability problem

0 references

The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs

0 references

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

0 references

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

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

Q3558598

0 references

Identifiers

DOI

10.33048/daio.2023.30.758

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6644082