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 vertexweighted 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 (1997) defined the weighted chromatic number of a vertexweighted graph G as the smallest weight of a proper coloring of G. 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 NPhard in general graphs. It remains NPhard 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 timecomplexity of computing this parameter in trees is still open.
The Exponential Time Hypothesis (ETH) states that 3SAT cannot be solved in subexponential time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of nnode trees has timecomplexity n O(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.
BibTeX  Entry
@InProceedings{araujo_et_al:LIPIcs:2014:4448,
author = {Julio Araujo and Nicolas Nisse and St{\'e}phane P{\'e}rennes},
title = {{Weighted Coloring in Trees}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {7586},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4448},
URN = {urn:nbn:de:0030drops44484},
doi = {10.4230/LIPIcs.STACS.2014.75},
annote = {Keywords: Weighted Coloring, Max Coloring, Exponential Time Hypothesis, 3SAT}
}
Keywords: 

Weighted Coloring, Max Coloring, Exponential Time Hypothesis, 3SAT 
Collection: 

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) 
Issue Date: 

2014 
Date of publication: 

05.03.2014 