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

zbMath1326.05047MaRDI QIDQ892049

Dmitriy S. Malyshev

Publication date: 18 November 2015

Published in: Sibirskie Èlektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL: http://semr.math.nsc.ru/v11/p811-822.pdf

zbMATH Keywords

computational complexityefficient algorithmhereditary classedge 3-colorability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Complexity classification of the edge coloring problem for a family of graph classes ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Unnamed Item ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs ⋮ Two complexity results for the vertex coloring problem ⋮ Critical hereditary graph classes: a survey ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs

This page was built for publication: The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices