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

DOI10.33048/daio.2023.30.758MaRDI QIDQ6644082

Dmitriy S. Malyshev, Oleg Duginov

Publication date: 27 November 2024

Published in: Diskretnyĭ Analiz i Issledovanie Operatsiĭ (Search for Journal in Brave)

zbMATH Keywords

computational complexitymonotone classedge-coloring problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs