On the performance guarantee of first fit for sum coloring

DOI10.1016/j.jcss.2018.08.002zbMath1408.68116OpenAlexW2890474798WikidataQ129207018 ScholiaQ129207018MaRDI QIDQ1628787

Asaf Levin, Leah Epstein

Publication date: 10 December 2018

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2018.08.002

zbMATH Keywords

approximation algorithmgraph coloringfirst fitchromatic sum number of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Edge-chromatic sum of trees and bounded cyclicity graphs
• On sum coloring and sum multi-coloring for restricted families of graphs
• Minimum sum edge colorings of multicycles
• Some perfect coloring properties of graphs
• On the sum coloring problem on interval graphs
• Claw-free graphs---a survey
• On chromatic sums and distributed resource allocation
• The chromatic sum of a graph: history and recent developments
• On sum coloring of graphs
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Sum coloring of bipartite graphs with bounded degree
• Sum edge coloring of multigraphs via configuration LP
• On some packing problem related to dynamic storage allocation
• Minimum Color Sum of Bipartite Graphs
• Improved bounds for scheduling conflicting jobs with minsum criteria
• Mathematical Foundations of Computer Science 2004

This page was built for publication: On the performance guarantee of first fit for sum coloring