Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes

DOI10.1016/j.dam.2015.01.022zbMath1311.05064arXiv1409.0893OpenAlexW2085493165MaRDI QIDQ2345603

Chính T. Hoàng, D. Adam Lazzarato

Publication date: 22 May 2015

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

Full work available at URL: https://arxiv.org/abs/1409.0893

zbMATH Keywords

graph coloring\(P_5\)-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (22)

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs ⋮ Colouring diamond-free graphs ⋮ The weighted coloring problem for two graph classes characterized by small forbidden induced structures ⋮ The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs ⋮ 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 square-free graphs without long induced paths. ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ Clique‐width: Harnessing the power of atoms ⋮ Star coloring of certain graph classes ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ Graphs with No Induced Five‐Vertex Path or Antipath ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Polynomial cases for the vertex coloring problem ⋮ Two complexity results for the vertex coloring problem ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size ⋮ $(2P_2,K_4)$-Free Graphs are 4-Colorable ⋮ Colouring square-free graphs without long induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The ellipsoid method and its consequences in combinatorial optimization
• Modular decomposition and transitive orientation
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• A Note on k-Colorability of P 5-Free Graphs
• Four classes of perfectly orderable graphs

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