Weighted Coloring in Trees

Julio Araujo 1, 2 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 {\it color}. For a vertex-weighted graph, the {\it weight of a color} is the maximum weight of its vertices. The {\it weight of a coloring} is the sum of the weights of its colors. Guan and Zhu defined the {\it 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. Therefore, the problem of computing the weighted chromatic number is NP-complete in general graphs. This problem remains NP-complete in some particular graph classes as bipartite graphs. In their seminal paper, Guan and Zhu asked whether the weighted chromatic number of bounded tree-width graphs (partial $k$-trees) can be computed in polynomial-time. Escoffier et al. designed a polynomial-time approximation scheme for computing the weighted chromatic number of partial $k$-trees (2006), and Kavitha and Mestre provided polynomial-time exact algorithms for sub-classes of trees (2009). 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^{\Theta(\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, even when $G$ is a forest.
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-00794622
Contributor : Nicolas Nisse <>
Submitted on : Thursday, March 7, 2013 - 1:02:51 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Sunday, April 2, 2017 - 10:05:14 AM

File

RR-8249.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00794622, version 2

Collections

Citation

Julio Araujo, Nicolas Nisse, Stéphane Pérennes. Weighted Coloring in Trees. [Research Report] RR-8249, INRIA. 2013. ⟨hal-00794622v2⟩

Share

Metrics

Record views

944

Files downloads

212