A coloring problem for weighted graphs

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

Authors: D. J. Guan, Xuding Zhu Edit this on Wikidata

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
• 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 (25)

• 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
• Saving colors and max coloring: some fixed-parameter tractability results
• On properly ordered coloring of vertices in a vertex-weighted graph
• 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
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
• Dual parameterization of weighted coloring
• 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
• 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
• Saving colors and max coloring: some fixed-parameter tractability results
• On the complexity of injective colorings and its generalizations
• Weighted Improper Colouring
• Weighted coloring in trees
• Weighted coloring in trees

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)