Weighted Coloring in Trees

Julio Araújo 1 Nicolas Nisse 1, 2 Stéphane Pérennes 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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-exponential 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.
Type de document :
Communication dans un congrès
31st Symposium on Theoretical Aspects of Computer Science (STACS), Mar 2014, Lyon, France. Dagstuhl Publishing, pp.75-86, 2014

Contributeur : Nicolas Nisse <>
Soumis le : mercredi 15 janvier 2014 - 14:03:12
Dernière modification le : mercredi 7 octobre 2015 - 01:15:01
Document(s) archivé(s) le : mardi 15 avril 2014 - 22:44:13


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00931523, version 1



Julio Araújo, Nicolas Nisse, Stéphane Pérennes. Weighted Coloring in Trees. 31st Symposium on Theoretical Aspects of Computer Science (STACS), Mar 2014, Lyon, France. Dagstuhl Publishing, pp.75-86, 2014. <hal-00931523>



Consultations de
la notice


Téléchargements du document