Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs

DOI10.1007/978-3-031-38906-1_22OpenAlexW4385357590MaRDI QIDQ6179424

Ian DeHaan, Zachary Friggstad

Publication date: 16 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-38906-1_22

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Cites Work

• Unnamed Item
• Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
• Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
• Complexity results for minimum sum edge coloring
• The maximum k-colorable subgraph problem for chordal graphs
• Zero knowledge and the chromatic number
• On chromatic sums and distributed resource allocation
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Sum coloring of bipartite graphs with bounded degree
• Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
• Sum edge coloring of multigraphs via configuration LP
• Minimum Color Sum of Bipartite Graphs
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
• Approximating Maximum Clique by Removing Subgraphs
• Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract)
• Programming Languages and Systems
• Approximation and Online Algorithms

This page was built for publication: Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs