Polynomial-time algorithms for minimum weighted colorings of (P₅, P₅)-free graphs and similar graph classes
From MaRDI portal
Publication:2345603
Recommendations
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- Two complexity results for the vertex coloring problem
- A Note on k-Colorability of P 5-Free Graphs
Cites work
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 1456953 (Why is no real title available?)
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- A Note on k-Colorability of P 5-Free Graphs
- A survey of the algorithmic aspects of modular decomposition
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- Four classes of perfectly orderable graphs
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- Modular decomposition and transitive orientation
- On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
- The ellipsoid method and its consequences in combinatorial optimization
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
Cited in
(25)- Graphs with No Induced Five‐Vertex Path or Antipath
- The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
- Colouring square-free graphs without long induced paths
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- 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 two hereditary graph classes
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- A coloring algorithm for \(4 K_1\)-free line graphs
- \((2P_2,K_4)\)-free graphs are 4-colorable
- Colouring square-free graphs without long induced paths
- 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
- Colouring diamond-free graphs
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
- Clique‐width: Harnessing the power of atoms
- Star coloring of certain graph classes
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
- A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
- Clique-width of graph classes defined by two forbidden induced subgraphs
- Two complexity results for the vertex coloring problem
- Polynomial cases for the vertex coloring problem
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- Fundamentals of Computation Theory
This page was built for publication: Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345603)
