A coloring problem for weighted graphs

DOI10.1016/S0020-0190(97)00002-1MaRDI QIDQ286971zbMATH OpenOpenAlexFDO

Authors 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

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)

Recommendations

• Weighted coloring in trees
• Weighted coloring in trees
• Weighted coloring: further complexity and approximability results
• Theoretical Computer Science

Cites work

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

Cited in

(25)

• scientific article; zbMATH DE number 4144006 (Why is no real title available?)
• Batch Coloring Flat Graphs and Thin
• Weighted coloring in trees
• On the max coloring problem
• Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs
• Polynomial approximation: a structural and operational study. (Abstract of thesis)
• Minimum cost and list homomorphisms to semicomplete digraphs
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• On properly ordered coloring of vertices in a vertex-weighted graph
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
• Saving colors and max coloring: some fixed-parameter tractability results
• On the complexity of injective colorings and its generalizations
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Clique clustering yields a PTAS for max-coloring interval graphs
• Clique partitioning of interval graphs with submodular costs on the cliques
• On the Grundy number of graphs with few \(P_4\)'s
• Weighted coloring in trees
• Weighted coloring: further complexity and approximability results
• Max-coloring of vertex-weighted graphs
• On the Max Coloring Problem
• Dual parameterization of weighted coloring
• Dual parameterization of weighted coloring
• Weighted Improper Colouring
• Max-coloring paths: tight bounds and extensions
• Saving colors and max coloring: some fixed-parameter tractability results

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)