A coloring problem for weighted graphs

DOI10.1016/S0020-0190(97)00002-1zbMath1336.05041OpenAlexW2029120932MaRDI QIDQ286971

F. Blanchet-Sadri, M. Dambrine

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00002-1

zbMATH Keywords

combinatorial problemsdesign of algorithmsweighted graphgreedy coloringoptimal coloringreal-time message transmission

Mathematics Subject Classification ID

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

Related Items (20)

Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results ⋮ Polynomial approximation: a structural and operational study. (Abstract of thesis) ⋮ On the complexity of injective colorings and its generalizations ⋮ Batch Coloring Flat Graphs and Thin ⋮ Max-coloring paths: tight bounds and extensions ⋮ Clique partitioning of interval graphs with submodular costs on the cliques ⋮ Dual parameterization of Weighted Coloring ⋮ Clique Clustering Yields a PTAS for max-Coloring Interval Graphs ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ On the max coloring problem ⋮ On the Grundy number of graphs with few \(P_4\)'s ⋮ Minimum cost and list homomorphisms to semicomplete digraphs ⋮ On the Max Coloring Problem ⋮ Clique clustering yields a PTAS for max-coloring interval graphs ⋮ Ruling out FPT algorithms for weighted coloring on forests ⋮ Max-coloring of vertex-weighted graphs ⋮ Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ Weighted coloring: further complexity and approximability results ⋮ Dual parameterization of weighted coloring

Cites Work

• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• The Linearity of First-Fit Coloring of Interval Graphs
• Effective coloration
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Tight Bounds for Dynamic Storage Allocation

This page was built for publication: A coloring problem for weighted graphs