Given an @math -vertex graph @math and two positive integers @math , the ( @math )-differential coloring problem asks for a coloring of the vertices of @math (if one exists) with distinct numbers from 1 to @math (treated as ), such that the minimum difference between the two colors of any adjacent vertices is at least @math . While it was known that the problem of determining whether a general graph is ( @math )-differential colorable is NP-complete, our main contribution is a complete characterization of bipartite, planar and outerplanar graphs that admit ( @math )-differential colorings. For practical reasons, we consider also color ranges larger than @math , i.e., @math . We show that it is NP-complete to determine whether a graph admits a ( @math )-differential coloring. The same negative result holds for the ( @math -differential coloring problem, even in the case where the input graph is planar.
The maximum differential coloring problem is a well-studied problem, which dates back in 1984, when @cite_5 introduced it under the name separation number'' and showed its NP-completeness. It is worth mentioning though that the maximum differential coloring problem is also known as dual bandwidth'' @cite_4 and anti-bandwidth'' @cite_13 , since it is the complement of the bandwidth minimization problem @cite_14 . Due to the hardness of the problem, heuristics are often used for coloring general graphs, e.g., LP-formulations @cite_9 , memetic algorithms @cite_0 and spectral based methods @cite_6 . The differential chromatic number is known only for special graph classes, such as Hamming graphs @cite_12 , meshes @cite_3 , hypercubes @cite_3 @cite_10 , complete binary trees @cite_7 , complete @math -ary trees for odd values of @math @cite_13 , other special types of trees @cite_7 , and complements of interval graphs, threshold graphs and arborescent comparability graphs @cite_2 . Upper bounds on the differential chromatic number are given by @cite_5 for connected graphs and by Miller and Pritikin @cite_20 for bipartite graphs. For a more detailed bibliographic overview refer to @cite_1 .
@cite_14 @cite_4 @cite_7 @cite_10 @cite_9 @cite_1 @cite_6 @cite_3 @cite_0 @cite_2 @cite_5 @cite_20 @cite_13 @cite_12
1520709705 2018399909 2154213027 2157562188
We study the maximum differential graph coloring problem, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of k-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs. Abstract We study the maximum differential coloring problem , where the vertices of an n -vertex graph must be labeled with distinct numbers ranging from 1 to n , so that the minimum absolute difference between two labels of any two adjacent vertices is maximized. As the problem is NP -hard for general graphs [16] , we consider planar graphs and subclasses thereof. We prove that the maximum differential coloring problem remains NP -hard, even for planar graphs. We also present tight bounds for regular caterpillars and spider graphs. Using these new bounds, we prove that the Miller–Pritikin labeling scheme [19] for forests is optimal for regular caterpillars and for spider graphs. We consider the following graph labeling problem, introduced by (J. Y-T. Leung, O. Vornberger, and J. D. Witthoff, On some variants of the bandwidth minimization problem. SIAM J. Comput. 13 (1984) 650–667). Let G be a graph of order n, and f a bijection from V(G) to the integers 1 through n. Let |f|, and define s(G), the separation number of G, to be the maximum of |f| among all such bijections f. We first derive some basic relations between s(G) and other graph parameters. Using a general strategy for analyzing separation number in bipartite graphs, we obtain exact values for certain classes of forests and asymptotically optimal lower bounds for grids and hypercubes. We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d>0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k>0, we call a coloring k-partially proper if every node v has at least min k,deg(v) neighbors with a different color. We show that for all d∈ 1,...,Δ , it is possible to compute a O(Δ2 d2)-coloring with defect d in time O(log*n) where Δ is the largest degree of the network graph. Similarly, for all k∈ 1,...,Δ , a k-partially proper O(k2)-coloring can be computed in O(log*n) rounds. As an application of our weak defective coloring algorithm, we obtain a faster deterministic algorithm for the standard vertex coloring problem on graphs with moderate degrees. We show that in time O(Δ+log*n), a (Δ+1)-coloring can be computed, a task for which the best previous algorithm required time O(Δ*log(Δ) + log*n). The same result holds for the problem of computing a maximal independent set.