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

DOI10.1016/J.TCS.2011.11.010zbMATH Open1232.68061OpenAlexW2017360257MaRDI QIDQ764335FDOQ764335

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

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

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)

Cites Work

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

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)