Search

A proper k-coloring of a graph G is a partition c = ( S i ) i ∈ [ 1 , k ] of V ( G ) into k stable sets S 1 , … , S k . Given a weight function w : V ( G ) → R + , the weight of a color S i is defined as w ( i ) = max v ∈ S i ⁡ w ( v ) and the weight of a coloring c as w ( c ) = ∑ i = 1 k w ( i ) . Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair ( G , w ), denoted by σ ( G , w ) , as the minimum weight of a proper coloring of G . For a positive integer r , they also defined σ ( G , w ; r ) as the minimum of w ( c ) among all proper r -colorings c of G . The complexity of determining σ ( G , w ) when G is a tree was open for almost 20 years, until Araújo et al. [SIAM J. Discrete Math., 2014] recently proved that the problem cannot be solved in time n o ( log ⁡ n ) on n -vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing σ ( G , w ) and σ ( G , w ; r ) when G is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis FPT ≠ W [ 1 ] . Building on the techniques of Araújo et al. , we prove that when G is a forest, computing σ ( G , w ) is W [ 1 ] -hard parameterized by the size of a largest connected component of G , and that computing σ ( G , w ; r ) is W [ 2 ] -hard parameterized by r . Our results rule out the existence of FPT algorithms for computing these invariants on trees or forests for many natural choices of the parameter. [ABSTRACT FROM AUTHOR]

Abstract: Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs. The problem is NP-complete for quasi-line graphs. For the subclass of fuzzy circular interval graphs however, one can compute the weighted coloring number in polynomial time using recent results of Chudnovsky and Ovetsky and of King and Reed. Whether one could actually compute an optimal weighted coloring of a fuzzy circular interval graph in polynomial time however was still open. We provide a combinatorial algorithm that computes weighted colorings and the weighted coloring number for fuzzy circular interval graphs efficiently. The algorithm reduces the problem to the case of circular interval graphs, then making use of an algorithm by Gijswijt to compute integer decompositions. [Copyright &y& Elsevier]