The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
From MaRDI portal
Publication:1996748
DOI10.1007/s11590-020-01593-0zbMath1473.05092OpenAlexW3027724754MaRDI QIDQ1996748
Panos M. Pardalos, O. O. Razvenskaya, Dmitriy S. Malyshev
Publication date: 26 February 2021
Published in: Optimization Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11590-020-01593-0
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)
Cites Work
- Unnamed Item
- Complexity of coloring graphs without paths and cycles
- Vertex coloring of graphs with few obstructions
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Minimum total coloring of planar graph
- 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
- A coloring problem on the \(n\)-cube
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- Structure and algorithms for (cap, even hole)-free graphs
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- On coloring a class of claw-free graphs.
- The intersection of two vertex coloring problems
- Colouring square-free graphs without long induced paths
- 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
- Colouring diamond-free graphs
- Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
- Optimal channel assignment with list-edge coloring
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- The class of (P7,C4,C5)‐free graphs: Decomposition, algorithms, and χ‐boundedness
- Two cases of polynomial-time solvability for the coloring problem
