Complexity results for minimum sum edge coloring

DOI10.1016/j.dam.2008.04.002zbMath1169.05382OpenAlexW1974098993MaRDI QIDQ1028432

Dániel Marx

Publication date: 30 June 2009

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

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

zbMATH Keywords

graph coloringNP-completenessminimum sum coloringminimum sum edge coloringMSEC

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ NP‐completeness of list coloring and precoloring extension on the edges of planar graphs ⋮ Chromatic Edge Strength of Some Multigraphs ⋮ Minimum sum set coloring of trees and line graphs of trees ⋮ Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs ⋮ On sum edge-coloring of regular, bipartite and split graphs ⋮ Minimum sum edge colorings of multicycles ⋮ Combinatorial algorithms for data migration to minimize average completion time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge-chromatic sum of trees and bounded cyclicity graphs
• The complexity of chromatic strength and chromatic edge strength
• Precoloring extension. I: Interval graphs
• A partial k-arboretum of graphs with bounded treewidth
• On the sum coloring problem on interval graphs
• The membership problem in jump systems
• On chromatic sums and distributed resource allocation
• Some APX-completeness results for cubic graphs
• Algorithm for the cost edge-coloring of trees
• 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
• Extending an edge-coloring
• Combinatorial Algorithms for Data Migration to Minimize Average Completion Time
• Minimum Color Sum of Bipartite Graphs
• Graph colorings with local constraints -- a survey
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
• Precoloring Extension III: Classes of Perfect Graphs
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• Approximation and Online Algorithms
• The edge-disjoint paths problem is NP-complete for series-parallel graphs

This page was built for publication: Complexity results for minimum sum edge coloring