Approximating maximum weight K-colorable subgraphs in chordal graphs

DOI10.1016/J.IPL.2008.12.007zbMATH Open1191.68860OpenAlexW1984307728MaRDI QIDQ976121FDOQ976121

Sambuddha Roy, Venkatesan T. Chakaravarthy

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.12.007

Recommendations

• The maximum k-colorable subgraph problem for chordal graphs
• On \(k\)-coloring of weighted circular-arc graphs
• A new polynomial-time algorithm for the maximum weighted (?(G) ? 1)-coloring problem in comparability graphs
• On 2-Subcolourings of Chordal Graphs
• The black-and-white coloring problem on chordal graphs

zbMATH Keywords

approximation algorithmsinterval graphschordal graphscoloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• On the \(k\)-coloring of intervals
• Linear degree extractors and the inapproximability of max clique and chromatic number
• The maximum k-colorable subgraph problem for chordal graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• A unified approach to approximating resource allocation and scheduling
• Title not available (Why is that?)
• Multi-phase algorithms for throughput maximization for real-time scheduling
• Programming Languages and Systems

Cited In (6)

• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Inductive graph invariants and approximation algorithms
• Improved Inapproximability Results for Maximum k-Colorable Subgraph
• On the complexity of the selective graph coloring problem in some special classes of graphs

This page was built for publication: Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs

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