Minimum sum edge colorings of multicycles

DOI10.1016/J.DAM.2009.04.020MaRDI QIDQ987666zbMATHOpenAlexFDO

Authors Jean Cardinal, Vlady Ravelomanana, Mario Valencia-Pabon

Publication date 13 August 2010

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

Full work available at URL https://doi.org/10.1016/j.dam.2009.04.020

zbMATH Keywords

graph coloringminimum sum coloringchromatic strength

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Recommendations

• Chromatic Edge Strength of Some Multigraphs
• Edge-chromatic sum of trees and bounded cyclicity graphs
• Approximation and Online Algorithms
• On sum coloring of graphs
• Approximation and Online Algorithms

Cites work

• scientific article; zbMATH DE number 4154469 (Why is no real title available?)
• scientific article; zbMATH DE number 5764868 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 1947053 (Why is no real title available?)
• Algorithms and Computation
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• Approximating min sum set cover
• Approximation results for the optimum cost chromatic partition problem
• Complexity results for minimum sum edge coloring
• Edge-chromatic sum of trees and bounded cyclicity graphs
• Minimal coloring and strength of graphs
• Minimum Color Sum of Bipartite Graphs
• On chromatic sums and distributed resource allocation
• On sum coloring of graphs
• On the cost chromatic number of outerplanar, planar, and line graphs
• On the sum coloring problem on interval graphs
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
• Sum coloring and interval graphs: A tight upper bound for the minimum number of colors
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• The complexity of chromatic strength and chromatic edge strength

Cited in

(8)

• Minimum sum set coloring of trees and line graphs of trees
• On the performance guarantee of first fit for sum coloring
• Chromatic Edge Strength of Some Multigraphs
• On sum edge-coloring of regular, bipartite and split graphs
• A note on polynomial algorithm for cost coloring of bipartite graphs with \(\Delta \leq 4\)
• Approximation and Online Algorithms
• Edge-chromatic sum of trees and bounded cyclicity graphs
• Minimum number of palettes in edge colorings

This page was built for publication: Minimum sum edge colorings of multicycles

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