Search

Given a graph G, a properk-coloring of 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 coloringc as w (c) = ∑ i = 1 k w (i) . Guan and Zhu (Inf Process Lett 61(2):77–81, 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. The problem of determining σ (G , w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time n o (log n) unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is σ (G , w) ≤ ∑ v ∈ V (G) w (v) - k ? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50–61, 2016), who provided an FPT algorithm running in time 2 O (k log k) · n O (1) , and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time 9 k · n O (1) , and prove that no algorithm in time 2 o (k) · n O (1) exists under the ETH. On the other hand, we present a kernel with at most (2 k - 1 + 1) (k - 1) vertices, and rule out the existence of polynomial kernels unless NP ⊆ coNP / poly , even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials. [ABSTRACT FROM AUTHOR]

Given a graph G , a proper k-coloring of G is a partition c = ( S i ) i ∈ [ 0 , k − 1 ] of V ( G ) into k stable sets S 0 , … , S k − 1 . 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 = 0 k − 1 w ( i ) . Guan and Zhu (1997) [11] 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. (2014) [1] 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, the decision problem of 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]

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]

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. 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. the 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 polynomial-time approximation scheme 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 subexponential time. We show that, assuming the 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. [ABSTRACT FROM AUTHOR]

The Hajós' Theorem (Wiss Z Martin Luther Univ Math-Natur Reihe, 10, pp 116-117, ) shows a necessary and sufficient condition for the chromatic number of a given graph $$G$$ to be at least $$k$$: $$G$$ must contain a $$k$$-constructible subgraph. A graph is $$k$$-constructible if it can be obtained from a complete graph of order $$k$$ by successively applying a set of well-defined operations. Given a vertex-weighted graph $$G$$ and a (proper) $$r$$-coloring $$c=\{C_1, \ldots , C_r\}$$ of $$G$$, the weight of a color class $$C_i$$ is the maximum weight of a vertex colored $$i$$ and the weight of $$c$$ is the sum of the weights of its color classes. The objective of the Weighted Coloring Problem [] is, given a vertex-weighted graph $$G$$, to determine the minimum weight of a proper coloring of $$G$$, that is, its weighted chromatic number. In this article, we prove that the Weighted Coloring Problem admits a version of the Hajós' Theorem and so we show a necessary and sufficient condition for the weighted chromatic number of a vertex-weighted graph $$G$$ to be at least $$k$$, for any positive real $$k$$. [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]

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. [Copyright &y& Elsevier]