Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions

DOI10.33048/daio.2020.27.668zbMath1493.05101OpenAlexW3127281415MaRDI QIDQ5090159

Dmitriy V. Gribanov, Dmitriy S. Malyshev, Dmitrii Mokeev

Publication date: 15 July 2022

Published in: Diskretnyi analiz i issledovanie operatsii (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/da957

zbMATH Keywords

computational complexityhereditary classweighted vertex coloring problem

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex coloring of graphs with few obstructions
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Coloring graphs characterized by a forbidden subgraph
• The coloring problem for classes with two small obstructions
• Two complexity results for the vertex coloring problem
• Polynomial cases for the vertex coloring problem
• Colouring vertices of triangle-free graphs without forests
• The strong perfect graph theorem
• Decomposition by clique separators
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• Polynomial-time approximation algorithms for the coloring problem in some cases
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Two cases of polynomial-time solvability for the coloring problem

This page was built for publication: Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions