On sum coloring of graphs

DOI10.1016/S0166-218X(02)00249-4zbMath1018.05035MaRDI QIDQ1811069

Mohammad R. Salavatipour

Publication date: 10 June 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial time algorithmNP-completechromatic sumedge strengthedge sum coloringoptimaum cost chromatic partitionoptimum coloringvertex strength

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (21)

Lower Bounds for the Minimal Sum Coloring Problem ⋮ Hybrid evolutionary search for the minimum sum coloring problem of graphs ⋮ The transportation problem with conflicts ⋮ On the performance guarantee of first fit for sum coloring ⋮ Minimum sum coloring problem: upper bounds for the chromatic strength ⋮ Chromatic Edge Strength of Some Multigraphs ⋮ Minimum sum set coloring of trees and line graphs of trees ⋮ On sum edge-coloring of regular, bipartite and split graphs ⋮ A branch-and-price algorithm for the minimum sum coloring problem ⋮ ILP models and column generation for the minimum sum coloring problem ⋮ Computing lower bounds for minimum sum coloring and optimum cost chromatic partition ⋮ An effective heuristic algorithm for sum coloring of graphs ⋮ Minimum sum edge colorings of multicycles ⋮ Minimum sum multicoloring on the edges of trees ⋮ A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph ⋮ On the minimum sum coloring of \(P_4\)-sparse graphs ⋮ On sum coloring of graphs ⋮ Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems ⋮ Complexity results for minimum sum edge coloring ⋮ Max-optimal and sum-optimal labelings of graphs ⋮ Minimum Sum Coloring of P4-sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On chromatic sums and distributed resource allocation
• On sum coloring of graphs
• Minimal coloring and strength of graphs
• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• Tight bounds on the chromatic sum of a connected graph
• Node-Deletion Problems on Bipartite Graphs
• The NP-Completeness of Edge-Coloring
• Computing the Minimum Fill-In is NP-Complete
• Minimum Color Sum of Bipartite Graphs
• NP completeness of finding the chromatic index of regular graphs

This page was built for publication: On sum coloring of graphs