Weighted Coloring in Trees

DOI10.1137/140954167zbMath1314.05059OpenAlexW2117000938MaRDI QIDQ5246102

Julio Araujo, Nicolas Nisse, Stéphane Pérennes

Publication date: 17 April 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/140954167

zbMATH Keywords

exponential time hypothesisbinomial treesmax coloringweighted coloringvertex-weighted graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Minimax problems in mathematical programming (90C47) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Related Items (8)

Weighted proper orientations of trees and graphs of bounded treewidth ⋮ Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results ⋮ Dual parameterization of Weighted Coloring ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ Ruling out FPT algorithms for weighted coloring on forests ⋮ Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs ⋮ Dual parameterization of weighted coloring ⋮ Parameterized complexity of list coloring and max coloring

This page was built for publication: Weighted Coloring in Trees