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

zbMATH Open1326.05047MaRDI QIDQ892049FDOQ892049

Authors: D. S. Malyshev 

Publication date: 18 November 2015

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

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

Recommendations

• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
• On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
• scientific article; zbMATH DE number 7656024
• Complexity classification of the edge coloring problem for a family of graph classes

zbMATH Keywords

computational complexityhereditary classefficient algorithmedge 3-colorability

Mathematics Subject Classification ID

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

Cited In (11)

• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• Title not available (Why is that?)
• Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• Critical hereditary graph classes: a survey
• A complexity dichotomy and a new boundary class for the dominating set problem
• The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions
• Complexity classification of the edge coloring problem for a family of graph classes
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• Two complexity results for the vertex coloring problem
• Classifying \(k\)-edge colouring for \(H\)-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q892049)