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

DOI10.1016/J.DAM.2018.04.006MaRDI QIDQ1671374zbMATH OpenOpenAlexWikidataFDO

Authors D. S. Malyshev

Publication date 6 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.04.006

zbMATH Keywords

coloring problemcomputational complexityhereditary classpolynomial-time algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
• Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
• Theoretical Computer Science
• Two complexity results for the vertex coloring problem

Cites work

• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Coloring graphs characterized by a forbidden subgraph
• Colouring diamond-free graphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Colouring vertices of triangle-free graphs without forests
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• 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
• The coloring problem for classes with two small obstructions
• The strong perfect graph theorem
• Two cases of polynomial-time solvability for the coloring problem
• Two complexity results for the vertex coloring problem
• Vertex coloring of graphs with few obstructions

Cited in

(9)

• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
• Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
• Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• Polynomial cases for the vertex coloring problem
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable

This page was built for publication: The weighted coloring problem for two graph classes characterized by small forbidden induced structures

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