Search

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i\in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1,\ldots, S_{k}$. Given a weight function $w: V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^{k}w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G,w)$, denoted by $\sigma(G,w)$, as the minimum weight of a proper coloring of $G$. For a positive integer $r$, they also defined $\sigma(G,w;r)$ as the minimum of $w(c)$ among all proper $r$-colorings $c$ of $G$. The complexity of determining $\sigma(G,w)$ when $G$ is a tree was open for almost 20 years, until Ara\'ujo 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 $\sigma(G,w)$ and $\sigma(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 \neq W[1]$. Building on the techniques of Ara\'ujo et al., we prove that when $G$ is a forest, computing $\sigma(G,w)$ is $W[1]$-hard parameterized by the size of a largest connected component of $G$, and that computing $\sigma(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., Comment: 14 pages, 4 figures

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.

Given a vertex-weighted graph G = (V,E;w), w(v) ≥ 0 for any v ∈ V , we consider a weighted version of the coloring problem which consists in finding a partition S = (S1, . . . , Sk) of the vertex set V of G into stable sets and minimizing k i=1 w(Si) where the weight of S is defined as max{w(v) : v ∈ S}. In this paper, we keep on with the investigation of the complexity and the approximability of this problem by mainly answering one of the questions raised by D. J. Guan and X. Zhu ("A Coloring Problem for Weighted Graphs", Inf. Process. Lett. 61(2):77-81 1997).

A basic problem in the design of mobile telephone networks is to assign sets of radio frequency bands (colours) to transmitters (vertices) to avoid interference. Often the transmitters are laid out like vertices of a triangular lattice in the plane. We investigate the corresponding colouring problem of assigning sets of colours of size p(v) to each vertex of the triangular lattice so that the sets of colours assigned to adjacent vertices are disjoint. A n-[p]colouring of a graph G is a mapping c from V(G) into the set of the subsets of {1,2,…,n} such that |c(v)|=p(v) and for any adjacent vertices u and v, c(u)∩c(v)=∅. We give here an alternative proof of the fact that every triangular-free induced subgraph of the triangular lattice is 5-[2]colourable. This proof yields a constant time distributed algorithm that finds a 5-[2]colouring of such a graph. We then give a distributed algorithm that finds a [p]colouring of a triangle-free induced subgraph of the triangular lattice with at most 5ωp(G)/4+3 colours.