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
85690038 1971217502 2064388010 2018399909 1520709705 2037252568 2020148023 2123342283 2092518753 2154213027 2174253040 2179389847
The Problem of minimizing the bandwidth of the nonzero entries of a sparse symmetric matrix by permuting its rows and columns and some related combinatorial problems are shown to be NP-Complete. The Hales numbered n-dimensional hypercube exhibits interesting recursive structures in n. These structures lead to a very simple proof of the well-known bandwidth formula for hypercubes proposed by Harper, whose proof was thought to be surprisingly difficult. Harper also proposed an optimal numbering for a related problem called the antibandwidth of hypercubes. In a recent publication, approximated the hypercube antibandwidth up to the third-order term. In this paper, we find the exact value in light of the above recursive structures. This article proposes a linear integer programming formulation and several heuristics based on GRASP and path relinking for the antibandwidth problem. In the antibandwidth problem, one is given an undirected graph with n nodes and must label the nodes in a way that each node receives a unique label from the set 1, 2,…,n , such that, among all adjacent node pairs, the minimum difference between the node labels is maximized. Computational results show that only small instances of this problem can be solved exactly (to optimality) with a commercial integer programming solver and that the heuristics find high-quality solutions in much less time than the commercial solver. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(3), 171–189 2011 © 2011 Wiley Periodicals, Inc. 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 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. The antibandwidth problem consists of placing the vertices of a graph on a line in consecutive integer points in such a way that the minimum difference of adjacent vertices is maximised. The problem was originally introduced in [J.Y.-T. Leung, O. Vornberger, J.D. Witthoff, On some variants of the bandwidth minimisation problem, SIAM Journal of Computing 13 (1984) 650-667] in connection with the multiprocessor scheduling problems and can also be understood as a dual problem to the well-known bandwidth problem, as a special radiocolouring problem or as a variant of obnoxious facility location problems. The antibandwidth problem is NP-hard, there are a few classes of graphs with polynomial time complexities. Exact results for nontrivial graphs are very rare. Miller and Pritikin [Z. Miller, D. Pritikin, On the separation number of a graph, Networks 19 (1989) 651-666] showed tight bounds for the two-dimensional meshes and hypercubes. We solve the antibandwidth problem precisely for two-dimensional meshes, tori and estimate the antibandwidth value for hypercubes up to the third-order term. The cyclic antibandwidth problem is to embed an n-vertex graph into the cycle C"n, such that the minimum distance (measured in the cycle) of adjacent vertices is maximised. This is a natural extension of the antibandwidth problem or a dual problem to the cyclic bandwidth problem. We start investigating this invariant for typical graphs and prove basic facts and exact results for the same product graphs as for the antibandwidth. The antibandwidth maximization problem (AMP) consists of labeling the vertices of a n-vertex graph G with distinct integers from 1 to n such that the minimum difference of labels of adjacent vertices is maximized. This problem can be formulated as a dual problem to the well known bandwidth problem. Exact results have been proved for some standard graphs like paths, cycles, 2 and 3-dimensional meshes, tori, some special trees etc., however, no algorithm has been proposed for the general graphs. In this paper, we propose a memetic algorithm for the antibandwidth maximization problem, wherein we explore various breadth first search generated level structures of a graph--an imperative feature of our algorithm. We design a new heuristic which exploits these level structures to label the vertices of the graph. The algorithm is able to achieve the exact antibandwidth for the standard graphs as mentioned. Moreover, we conjecture the antibandwidth of some 3-dimensional meshes and complement of power graphs, supported by our experimental results. We give a simple proof that the obvious necessary conditions for a graph to contain the kth power of a Hamiltonian path are sufficient for the class of interval graphs. The proof is based on showing that a greedy algorithm tests for the existence of Hamiltonian path powers in interval graphs. We will also discuss covers by powers of paths and analogues of the Hamiltonian completion number. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 31–38, 1998 We consider the following variants of the bandwidth minimization problem: (1) the cycle-bandwidth problem which for a given graph G and positive integer k, asks if there is a circular layout such that every pair of adjacent vertexes have a distance at most k, (2) the separation problem which asks if there is a linear layout such that every pair of adjacent vertexes have a distance greater than k, and (3) the cycle-separation problem which asks if there is a circular layout such that every pair of adjacent vertexes have a distance greater than k.We show that the cycle-bandwidth problem is NP-complete for each fixed @math the separation and cycle-separation problems are both NP-complete for each fixed @math , and the directed separation problem is NP-complete for arbitrary k. We give polynomial time algorithms for several special cases of the directed separation problem. Finally, we show the relationships of the directed separation problem with several scheduling problems by giving reduct... 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. The antibandwidth problem is to label vertices of a n-vertex graph injectively by 1,2,3,...n, so that the minimum difference between labels of adjacent vertices is maximised. The problem is motivated by the obnoxious facility location problem, radiocolouring, work and game scheduling and is dual to the well known bandwidth problem. We prove exact results for the antibandwidth of complete k-ary trees, k even, and estimate the parameter for odd k up to the second order term. This extends previous results for complete binary trees. The antibandwidth problem is to label vertices of graph G(V,E) bijectively by integers 0,1,…,|V|−1 in such a way that the minimal difference of labels of adjacent vertices is maximised. In this paper we study the antibandwidth of Hamming graphs. We provide labeling algorithms and tight upper bounds for general Hamming graphs ∏k=1dKnk. We have exact values for special choices of ni's and equality between antibandwidth and cyclic antibandwidth values.