A coloring problem for weighted graphs

DOI10.1016/S0020-0190(97)00002-1zbMATH Open1336.05041OpenAlexW2029120932MaRDI QIDQ286971FDOQ286971

D. J. Guan, Xuding Zhu

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

Recommendations

• Weighted coloring in trees
• Weighted coloring in trees
• Ruling out FPT algorithms for weighted coloring on forests
• Weighted coloring: further complexity and approximability results
• Theoretical Computer Science

zbMATH Keywords

combinatorial problemsgreedy coloringweighted graphdesign of algorithmsoptimal coloringreal-time message transmission

Mathematics Subject Classification ID

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

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

Cited In (22)

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

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

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