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

DOI10.1016/j.tcs.2011.11.010zbMath1232.68061OpenAlexW2017360257MaRDI QIDQ764335

Allan Borodin, Bryce Zimny, Yuli Ye, Ioana Ivan

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

graph algorithmsapproximation algorithmsNP-hardnessinterval graphsgreedy algorithmssum coloringgeometric intersection graphsclawfree graphsunit disk graphspriority lower boundsum multi-coloring

Mathematics Subject Classification ID

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

Related Items

On the performance guarantee of first fit for sum coloring ⋮ Batch Coloring of Graphs ⋮ Greedy matching: guarantees and limitations ⋮ Batch coloring of graphs ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Models of greedy algorithms for graph problems
• Priority algorithms for graph optimization problems
• Zero knowledge and the chromatic number
• On the sum coloring problem on interval graphs
• A short proof that `proper = unit'
• On chromatic sums and distributed resource allocation
• (Incremental) priority algorithms
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• The Roberts characterization of proper and unit interval graphs
• Short Models for Unit Interval Graphs
• Elimination Graphs
• Universality considerations in VLSI circuits
• Minimum Color Sum of Bipartite Graphs
• Sum Multicoloring of Graphs
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
• Improved bounds for scheduling conflicting jobs with minsum criteria
• Sur le coloriage des graphs