Skip to Main content Skip to Navigation
New interface
Journal articles

Weighted Coloring in Trees

Julio Araujo 1 Nicolas Nisse 2 Stéphane Pérennes 2 
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G (1997). If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. Max Coloring Problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes, in particular, there exists a PTAS for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The Exponential Time Hypothesis (ETH) states that 3-SAT cannot be solved in sub-exponen-tial time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity n Θ(log n) . Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph G, it is hard to combine colorings of its connected components.
Document type :
Journal articles
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01109194
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Sunday, January 25, 2015 - 2:38:27 PM
Last modification on : Thursday, August 4, 2022 - 4:58:23 PM
Long-term archiving on: : Friday, September 11, 2015 - 9:15:22 AM

File

journal.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Julio Araujo, Nicolas Nisse, Stéphane Pérennes. Weighted Coloring in Trees. SIAM Journal on Discrete Mathematics, 2014, 28 (4), pp.2029 - 2041. ⟨10.1137/140954167⟩. ⟨hal-01109194⟩

Share

Metrics

Record views

186

Files downloads

179