On sum coloring and sum multi-coloring for restricted families of graphs

DOI10.1016/J.TCS.2011.11.010MaRDI QIDQ764335zbMATH OpenOpenAlexFDO

Authors Allan Borodin, Ioana Ivan, Yuli Ye, Bryce Zimny

Publication date 13 March 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.11.010

zbMATH Keywords

approximation algorithmsgraph algorithmsinterval graphsgreedy algorithmsNP-hardnesssum coloringgeometric intersection graphsclawfree graphsunit disk graphspriority lower boundsum multi-coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Sum Multicoloring of Graphs
• scientific article; zbMATH DE number 1998817
• On the sum coloring problem on interval graphs
• On the performance guarantee of first fit for sum coloring

Cites work

• scientific article; zbMATH DE number 1947053 (Why is no real title available?)
• scientific article; zbMATH DE number 1929966 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• scientific article; zbMATH DE number 2230206 (Why is no real title available?)
• (Incremental) priority algorithms
• A short proof that `proper = unit'
• Elimination Graphs
• Improved bounds for scheduling conflicting jobs with minsum criteria
• Minimum Color Sum of Bipartite Graphs
• Models of greedy algorithms for graph problems
• On chromatic sums and distributed resource allocation
• On the sum coloring problem on interval graphs
• Priority algorithms for graph optimization problems
• Short models for unit interval graphs
• Sum Multicoloring of Graphs
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Sur le coloriage des graphs
• The Roberts characterization of proper and unit interval graphs
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
• Universality considerations in VLSI circuits
• Zero knowledge and the chromatic number

Cited in

(6)

• Any-order online interval selection
• On the performance guarantee of first fit for sum coloring
• Batch coloring of graphs
• Batch Coloring of Graphs
• A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
• Greedy matching: guarantees and limitations

This page was built for publication: On sum coloring and sum multi-coloring for restricted families of graphs

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