Развлекательные | Consumer Reports – July 2018 - True PDF - zeke23[TGx] | Michael Boisvert

A note on maximum differential coloring of planar graphs

A note on maximum differential coloring of planar graphs

Journal of Discrete Algorithms 29 (2014) 1–7 Contents lists available at ScienceDirect Journal of Discrete Algorithms www.elsevier.com/locate/jda A...

302KB Sizes 0 Downloads 6 Views

Recommend Documents

Total coloring of planar graphs of maximum degree eight
The minimum number of colors needed to properly color the vertices and edges of a graph G is called the total chromatic

The Game Coloring Number of Planar Graphs
This paper discusses a variation of the game chromatic number of a graph: the game coloring number. This parameter provi

A note on list improper coloring of plane graphs
A list-assignment L to the vertices of G is an assignment of a set L(v) of colors to vertex v for every v∈V(G) . An

Equitable coloring planar graphs with large girth
A proper vertex coloring of a graph G is equitable if the size of color classes differ by at most one. The equitable chr

On acyclic edge coloring of planar graphs without intersecting triangles
Let Δ denote the maximum degree of a graph. Fiamčík first and then Alon et al. again conjectured that every graph is ac

A linear 5-coloring algorithm of planar graphs
A simple linear algorithm is presented for coloring planar graphs with at most five colors. The algorithm employs a recu

Acyclic vertex coloring of graphs of maximum degree six
In this paper, we prove that every graph with maximum degree six is acyclically 10-colorable, thus improving the main re

Scaling laws for maximum coloring of random geometric graphs
We examine maximum vertex coloring of random geometric graphs, in an arbitrary but fixed dimension, with a constant numb

Acyclic edge coloring of planar graphs with Δ colors
An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. In 1978, it was conjectured th

Acyclic edge coloring of planar graphs with large girth
Acyclic coloring problem is a specialized problem that arises in the efficient computation of Hessians. A proper edge co

Journal of Discrete Algorithms 29 (2014) 1–7

Contents lists available at ScienceDirect

Journal of Discrete Algorithms www.elsevier.com/locate/jda

A note on maximum differential coloring of planar graphs M.A. Bekos a , M. Kaufmann a , S. Kobourov b , S. Veeramoni b,∗ a b

Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Germany Dept. of Computer Science, University of Arizona, Tucson, AZ, USA

a r t i c l e

i n f o

Article history: Received 25 October 2013 Received in revised form 10 March 2014 Accepted 24 June 2014 Available online 17 July 2014 Keywords: Antibandwidth Separation number Graph labeling Caterpillar graph Spider graph

a b s t r a c t 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. © 2014 Elsevier B.V. All rights reserved.

1. Introduction The four color theorem states that only four colors are needed to color any map, so that no neighboring countries share the same color. However, if the countries in the map are not all contiguous, then the result no longer holds [6]. In order to avoid ambiguity, this necessitates the use of a unique color for each country. As a result, the number of colors needed is equal to the number of countries. Given a map, define the country graph G = ( V , E ) to be the graph where countries are vertices and two countries are connected by an edge if they share a nontrivial border. In the maximum differential coloring problem [16] the goal is to find a labeling of the n vertices of graph G with distinct numbers ranging from 1 to n (treated as colors), which maximizes the absolute label difference among adjacent vertices. More formally, let C = {c | c : V → {1, 2, . . . , | V |}} be the set of one-to-one functions for labeling the vertices of G. For any c ∈ C , the differential coloring achieved by c is min(i , j )∈ E |c (i ) − c ( j )|. We seek the labeling function c ∈ C that achieves the maximum differential coloring: DC(G ) = maxc ∈C min(i , j )∈ E |c (i ) − c ( j )|, which is the differential chromatic number of G. We also say that G admits a differential coloring of value k, if there is some labeling function c ∈ C so that min(i , j )∈ E |c (i ) − c ( j )| = k. The maximum differential coloring problem is in a sense the opposite of the well-studied bandwidth minimization problem, which is known to be NP-complete [20,21]. Optimal algorithms for the bandwidth minimization problem are known only for restricted classes of graphs, e.g., caterpillars with hair length 1 [18], caterpillars with hair length 3 [1], chain graphs [14], co-graphs [28], bipartite permutation graphs [11], AT-free graphs [8]. As in many graph theoretic maximization vs minimization problems (e.g., shortest vs longest path), results for bandwidth minimization do not translate into results for maximum differential coloring. Although the maximum differential coloring problem is less known than the bandwidth minimization problem, it has received considerable attention recently. In addition to map-coloring [6], the problem is motivated by the

*

Corresponding author. E-mail addresses: [email protected] (M.A. Bekos), [email protected] (M. Kaufmann), [email protected] (S. Kobourov), [email protected] (S. Veeramoni). http://dx.doi.org/10.1016/j.jda.2014.06.004 1570-8667/© 2014 Elsevier B.V. All rights reserved.

2

M.A. Bekos et al. / Journal of Discrete Algorithms 29 (2014) 1–7

radio frequency assignment problem, where n transmitters have to be assigned n frequencies, so that interfering transmitters have frequencies as far apart as possible [10]. 1.1. Previous work The maximum differential coloring problem was initially studied in the context of multiprocessor scheduling under the name “separation number” by Leung et al. [16], who showed that the problem is NP-complete. Twenty years later, Yixun et al. [29] studied the same problem under the name “dual-bandwidth” and gave several upper bounds, including the following simple bound for connected graphs: DC-Property 1. For any connected graph G, DC(G ) ≤  n2  [29]. The proof is straightforward: one of the vertices of G has to be labeled  n2 and since G is connected that vertex must have at least one neighbor which (regardless of its label) would make the difference along that edge at most  n2 . The maximum differential coloring problem is also known as the “anti-bandwidth problem” [3]. Heuristics for the maximum differential coloring problem have been suggested by Duarte et al. [5] using LP-formulation, by Bansal et al. [2] using memetic algorithms and by Hu et al. [12] using spectral based methods. Another line of research focuses on solving the maximum differential coloring problem optimally for special classes of graphs, e.g., Hamming graphs [4], meshes [25], hypercubes [23,26], complete binary trees [27] and complete k-ary trees for odd values of k [3]. Isaak et al. [13] give a greedy algorithm for the differential chromatic number of complement of interval and threshold graphs by computing the k-th power of a Hamiltonian path. Weili et al. [27] compute the differential chromatic number for what they call “caterpillars” (but which differ from the standard graph-theoretic caterpillars). Miller and Pritikin [19] describe a labeling scheme which, for a forest G with bipartition U and V , gives a differential coloring value equal to the size of the smaller vertex set, i.e., min{|U |, | V |}. This approach can be summarized as follows. Say, without loss of generality, that |U | ≤ | V |. The vertices in U are labeled with labels from the “minority interval” I min = [1, |U |], while the vertices in V are labeled with labels from the “majority interval” I maj = [|U | + 1, | V |]. Since the average degree of the vertices in V is (|U | + | V | − 1)/| V | < 2, there exists at least one vertex in V , say v, with degree ≤ 1. Based on the vertex v, a vertex u ∈ U is chosen as follows: If deg ( v ) = 1, then u is the neighbor of v. Otherwise, u is arbitrarily chosen from U . Both v and u are then labeled with the smallest available labels from I maj and I min , respectively, and removed from G. This procedure is repeated until U is empty. The remaining vertices in V (if any) are labeled with the remaining available labels in I maj . Note that when a vertex u ∈ U is labeled, a vertex v ∈ V is also labeled. Hence, as long as U is non-empty, the number of labeled vertices of U is equal to the number of labeled vertices of V . This implies that the minimum label difference between any two neighboring vertices in G is at least |U |. Equitable coloring [9] is also related to differential coloring. Formally, an equitable coloring is an assignment of colors to the vertices of a graph, so that no two adjacent vertices have the same color and the number of vertices in any two color classes differ by at most one. The problem of deciding whether a graph admits an equitable coloring with no more than three colors is NP-complete [15]. If a graph G has differential chromatic number k, then the vertices labeled [1, k], [k + 1, 2k] · · · form equitably colored classes and so G has an equitable coloring with  nk  + 1 colors. Lin et al. [17] n describe a (sub-optimal) labeling for connected bipartite graphs with a differential coloring of value  Δ , where Δ is the max degree, using the relationship between the anti-bandwidth problem and the equitable coloring problem. Another related problem is the channel assignment problem [24], in which each edge has a weight and the objective is to find a labeling of the vertices, so that the difference between the labels of the endpoints of each edge is at least equal to its weight. However, the same label can be used by multiple vertices. 1.2. Preliminaries Let G = ( V , E ) be an undirected graph. We denote the number of vertices of G by n, i.e., n = | V |. The degree of vertex u ∈ V is denoted by d(u ). The degree of graph G is then defined as: Δ(G ) = maxu ∈ V d(u ). A caterpillar is a tree in which removing all leaves results in a path; see Fig. 1a. Thus, a caterpillar consists of a simple path, called the “spine”, and each spine vertex is adjacent to a certain number of leaves, called the “legs”. In our algorithms we assume that spine vertices are indexed in the order they appear along the spine. Hence, an odd-indexed (even-indexed) spine vertex is one that appears in an odd-indexed (even-indexed) position along the spine. In caterpillars, Δ refers to the maximum number of legs of any spine vertex. In a regular caterpillar, every spine vertex has the same number of legs. A spider is a graph with a center vertex connected to several disjoint paths; see Fig. 1b. The vertices of a spider have levels, according to their distance from the center. In a spider, N e , N o and Nl denote the number of even level, number of odd level and number of vertices in level l, respectively. A radius-k star graph is a spider with all paths of the same length k; see Fig. 1c.

M.A. Bekos et al. / Journal of Discrete Algorithms 29 (2014) 1–7

3

Fig. 1. Illustration of (a) a caterpillar, (b) a spider (c) a radius-3 star.

Fig. 2. (a) An instance G = ( V , E ) of the 3-coloring problem; (b) an instance G = ( V , E ) of the maximum differential coloring problem constructed based on graph G; (c) the differential labeling of G , in the case where G is 3-colorable.

1.3. Paper structure This paper is structured as follow: In Section 2, we prove that the differential coloring problem is NP-hard even for planar graphs (Theorem 1). In Section 3, we present tight upper bounds for regular caterpillars (Theorem 2) and spiders (Theorem 3). We conclude in Section 4 with open problems and future work. 2. Differential coloring is NP-hard for planar graphs In this section, we prove that the differential coloring problem is NP-hard even for planar graphs. Theorem 1. Given a planar graph G = ( V , E ) and a positive integer k ≤ | V |, it is NP-hard to determine G has differential coloring of value at least k. Proof. In order to prove that the problem is NP-hard, we employ a reduction from the well-known 3-coloring problem, which is NP-complete for planar graphs [7]. More precisely, let G = ( V , E ) be an instance of the 3-coloring problem mentioned above, i.e., graph G is an n-vertex planar graph. In the following, we will construct a new planar graph G , so that G has differential coloring of value at least n if and only if G is 3-colorable. Graph G = ( V , E ) is constructed by attaching a path v → v 1 → v 2 to each vertex v ∈ V of G; see Figs. 2a and 2b. Hence, we can assume that V = V ∪ V 1 ∪ V 2 , where V is the vertex set of G, V 1 contains the first vertex of each 2-length path and V 2 the second ones. Clearly, G is planar on 3n vertices. Since G is a subgraph of G , G is 3-colorable if G is 3-colorable. On the other hand, if G is 3-colorable, then G is also 3-colorable; for each vertex v ∈ V , simply color its neighbors v 1 and v 2 with two distinct colors different from the color of v. Next, we show that G is 3-colorable if and only if G has differential coloring of value at least n. First assume that G has a differential coloring of value at least n and let l : V → {1, 2, . . . , 3n} be the respective labeling. Let u ∈ V be a vertex of G . We assign a color c (u ) to u as follows: – If 1 ≤ l(u ) ≤ n, then c (u ) = 1 – If n + 1 ≤ l(u ) ≤ 2n, then c (u ) = 2 – If 2n + 1 ≤ l(u ) ≤ 3n, then c (u ) = 3 Since the labeling l guarantees a differential coloring of value at least n, no two vertices with the same color are adjacent. Hence, coloring c is a 3-coloring for G . Now, consider the case where G is 3-colorable. Let C i ⊆ V be the set of vertices of the input graph G with color i, i = 1, 2, 3. Clearly, C 1 ∪ C 2 ∪ C 3 = V . We compute a labeling l of the vertices of graph G as follows; see Fig. 2c: – Vertices in C 1 are assigned labels from 1 to |C 1 |. – Vertices in C 2 are assigned labels from n + |C 1 | + 1 to n + |C 1 | + |C 2 |. – Vertices in C 3 are assigned labels from 2n + |C 1 | + |C 2 | + 1 to 2n + |C 1 | + |C 2 | + |C 3 |.

4

M.A. Bekos et al. / Journal of Discrete Algorithms 29 (2014) 1–7

– – – –

For For For For

a a a a

vertex vertex vertex vertex

v1 ∈ V 1 v1 ∈ V 1 v1 ∈ V 1 v2 ∈ V 2

neighboring neighboring neighboring neighboring

to to to to

a a a a

vertex vertex vertex vertex

v ∈ C 1 , l( v 1 ) = l( v ) + n. v ∈ C 2 , l( v 1 ) = l( v ) − n. v ∈ C 3 , l( v 1 ) = l( v ) − 2n. v 1 ∈ V 1 , l ( v 2 ) = l ( v 1 ) + n + |C 2 |.

From the above case analysis, it follows that the label difference between (i) any two vertices in G, (ii) a vertex v 1 ∈ V 1 and its neighbor v ∈ V , and, (iii) a vertex v 1 ∈ V 1 and its neighbor v 2 ∈ V 2 is at least n. Thus G has differential coloring of value at least n. 2 3. Upper bounds for regular caterpillars and spiders In this section, we establish new upper bounds for DC(G ), when G is a regular caterpillar or a spider. Then, we show that the Miller–Pritikin labeling scheme is optimal for these classes of graphs. We start by demonstrating an intuitive property for the labeling of Δ-regular caterpillars of a certain differential labeling value. Lemma 1. Let G be a Δ-regular caterpillar with n vertices. If G admits a differential labeling of value c ∗ =  n−Δ + 1, then no spine 2 vertex is labeled in the interval [ n−Δ ,  n+Δ ]. 2 2

Proof. Assume to the contrary that i ∈ [ n−Δ ,  n+Δ ] is a spine vertex label. Consider the labels that can be assigned to 2 2 the Δ legs of i (with a slight abuse of notation i also refers to the vertex labeled i). To achieve value c ∗ the label for a leg of i can either lie in the interval L = [1, i − ( n−Δ + 1)] or in the interval H = [i +  n−Δ + 1, n]. We consider three cases 2 2 for the label of i. Case 1. i =  n−Δ and i =  n+Δ . In this case, the total number of labels in L and H is: 2 2



i−

n−Δ



2

        n−Δ n−Δ +1 +n− i + =n− 2 +1 2 2   = n − 2k(Δ + 1) + 3

= n − (n + 2 − Δ) = Δ − 2. Case 2. i =  n−Δ . In this case, L is empty and all leg labels lie in interval H . Hence, the total number of labels in H is: 2



n− 2·



n−Δ 2



   = n − 2 · k · (Δ + 1) + 1       = (2k + 1) · (Δ + 1) − 2 · k · (Δ + 1) + 1 = Δ − 1.

Case 3. i =  n+Δ . In this case, H is empty and all leg labels lie in interval L. Similarly to the previous case, the total number 2 of labels in L is: i − ( n−Δ + 1) = Δ − 1. 2

In all cases the labels for the legs of i are insufficient. So, we have a contradiction.

2

The following theorem provides an upper bound for DC(G ), in the case where G is a Δ-regular caterpillar. Theorem 2. Let G be a Δ-regular caterpillar with n vertices. If G has an odd number of spine vertices, then DC(G ) ≤  n−Δ . Otherwise 2 DC(G ) ≤  n2 . Proof. If G has an even number of spine vertices, then by DC-Property 1 it follows that DC(G ) ≤  n2 . We will show that,

when G has an odd number of spine vertices, DC(G ) ≤  n−Δ . Let the number of spine vertices be s = 2k + 1, for some 2

k ≥ 1. Then, the total number of vertices of G is n = (2k + 1)(Δ + 1). Note that  n−Δ = 1 + k(Δ + 1). 2

For a proof by contradiction assume that there exists a labeling of value c ∗ =  n−Δ + 1. Then, by Lemma 1, it follows 2

that labels of spine vertices either lie in the interval L s = [1,  n−Δ − 1] or in the interval H s = [ n+Δ + 1, n]. Observe that 2 2

the maximum difference between any two elements in the interval L s is  n−Δ − 2. This means that in order to achieve 2 differential coloring c ∗ , adjacent spine vertices cannot both have labels in the interval L s . Similarly, adjacent spine vertices cannot both have labels in the interval H s , as the maximum difference between two elements in H s is n − ( n+Δ + 1) = 2

n − ( n−Δ + Δ + 1) = n − (k · (Δ + 1) + 1 + Δ + 1) =  n−Δ < c∗ . 2 2

M.A. Bekos et al. / Journal of Discrete Algorithms 29 (2014) 1–7

5

Since adjacent spine vertices cannot both have labels from the same interval (L s , or H s ), it follows that the labels of spine vertices must alternate between intervals L s and H s . Then for the labels of the 2k + 1 spine vertices, one of the intervals contributes k + 1 labels and other interval contributes k labels. Assume without loss of generality that L s contributes k + 1 labels. In order to achieve differential coloring c ∗ , the (k + 1)Δ legs of these spine vertices must all have labels in the interval I = [ n−Δ + 2, n]. As Δ ≥ 1, interval I ⊇ H s , and so I must also contain the k labels H s contributes for spine 2 vertices. Thus, in total I must contain at least (k + 1)Δ + k labels. However, the size of the interval I is:



1+n−

n−Δ 2



      + 2 = 1 + (2k + 1) · (Δ + 1) − k · (Δ + 1) + 1 − 2 =k·Δ+k+Δ−1 < (k + 1)Δ + k

This is a contradiction, which concludes the proof.

2

Based on Theorem 2, we can show that the Miller–Pritikin labeling scheme is optimal for regular caterpillars. Corollary 1. The Miller–Pritikin labeling scheme is optimal for regular caterpillars. Proof. Let G be a regular caterpillar on n vertices. First, consider the case where G has an even number of spine vertices, say s = 2k for some k ≥ 1. G is a bipartite graph whose vertices form two disjoint sets U and V , where U consists of the k odd-indexed spine vertices and the kΔ legs of the even-indexed spine vertices, and, V consists of the k even-indexed spine vertices and the kΔ legs of the odd-indexed spine vertices. So, |U | = | V | = k + kΔ = n2 . Since the Miller–Pritikin labeling scheme yields a labeling with value equal to the size of the smaller vertex set, the labeling is optimal by DC-Property 1. Now, consider the case where G has an odd number of spine vertices, say s = 2k + 1 for some k ≥ 1. In this case, U consists of the k even-indexed spine vertices and the (k + 1)Δ legs of the odd-indexed spine vertices, and, V consists of k + 1 odd-indexed spine vertices and the kΔ legs of the even-indexed spine vertices. So, |U | = k + (k + 1)Δ and | V | = k + 1 + kΔ, and min{|U |, | V |} = k + 1 + kΔ =  n−Δ . Thus, by Theorem 2 the Miller–Pritikin labeling scheme is optimal. 2 2 Next we present a tight upper bound for spider graphs, beginning with several simple observations about this graph class. Let p be the number of paths connected to the center vertex v c in a spider graph G. Recall that by N e , N o and Nl we denote the number of even level, number of odd level and number of vertices in level l, respectively. Then, the number of vertices of G is:

n = Ne + No + 1

(1)

Each of the p paths of G starts with an odd level vertex and alternates between even and odd levels. It follows that on each path the number of odd level vertices is at most one more than the even level vertices. Summing over all p paths we get:

No − Ne ≤ p

(2)

In the following lemma, we provide a property of labeling of a spider graph with differential labeling value c ∗ = N e + 2. Lemma 2. Let G be a spider graph with N e even level vertices. If G admits a differential labeling of value c ∗ = N e + 2, then the label of the center vertex is not in the interval [ N e + 1, N e + p + 1]. Proof. For the sake of contradiction, let i ∈ [ N e + 1, N e + p + 1] be the label of the center vertex and consider the labels that can be assigned to the p vertices of level 1. To achieve a differential coloring of value c ∗ , the labels of the level-1 vertices can either lie in the interval L = [1, i − ( N e + 2)] or in the interval H = [ N e + 2 + i , n]. We consider three cases for the values of i. Case 1. i = N e + 1 and i = N e + p + 1. Then, by Eqs. (1) and (2) the total number of labels in L and H is:

i − N e − 2 + n − (i + N e + 2) + 1 = n − 2N e − 3

= N e + N o + 1 − 2N e − 3 = N o − N e − 2 ≤ p − 2. Case 2. i = N e + 1. In this case, L is empty and all labels of level-1 vertices lie in H . By Eqs. (1) and (2), the total number of labels in H is:

6

M.A. Bekos et al. / Journal of Discrete Algorithms 29 (2014) 1–7

n − ( i + N e + 2) + 1 = n − ( N e + 1 + N e + 2) + 1

= N e + N o + 1 − ( N e + 1 + N e + 2) + 1 = N o − N e − 1 ≤ p − 1. Case 3. i = N e + p + 1. In this case, H is empty and all labels of level-1 vertices lie in L. Similarly to the previous case, the total number of labels in L is: i − N e − 2 = N e + p + 1 − N e − 2 = p − 1. In all cases the number of labels is less than p, which is a contradiction that completes the proof.

2

The following theorem provides an upper bound for DC(G ), in the case where G is a spider graph. Theorem 3. If G is a spider graph with N e even level vertices, then DC(G ) ≤ N e + 1. Proof. For a proof by contradiction suppose that there exists a labeling of value c ∗ = N e + 2. Then, by Lemma 2, the center label either lies in interval L c = [1, N e ] or in interval H c = [ N e + p + 2, n]. Let us first assume that the center label lies in L c . In this case, the level-1 vertices should lie in the interval I = [ N e + 3, n]. Note that in order to achieve a differential coloring of value c ∗ = N e + 2, adjacent vertices from neighboring levels 2 j and 2 j + 1 cannot both lie in the interval [1, N e + 2]. Also, N 2 j +1 ≤ N 2 j . It follows that the labels of at least N 2 j +1 vertices lie in the interval I . So, interval I must contain at least N 1 + N 3 + · · · = N o elements. The contradiction follows from the size of the interval I , which is:

n − Ne − 3 + 1 = Ne + No + 1 − Ne − 3 + 1

= No − 1 Now, assume that the center lies in the interval H c . An analogous argument shows that the interval I = [1, n − N e − 2] must contain at least N o elements, which is more than the size of I , leading to a contradiction. As both cases result in contradictions, this completes the proof of Theorem 3. 2 Based on Theorem 3, we can show that the Miller–Pritikin labeling scheme is optimal for spider graphs. Corollary 2. The Miller–Pritikin labeling scheme is optimal for spiders. Proof. Let G be a spider graph. Clearly, G is a bipartite graph whose vertices form disjoint sets U and V , where the even level vertices and the center vertex form U and the odd level vertices form V . Labeling G with the Miller–Pritikin scheme gives a differential coloring of value at least m = min{|U |, | V |} = min{ N e + 1, N o }. We now prove that m is optimal. We have that N e ≤ N o . If N e = N o , then m = N o . By DC-Property 1, it follows that DC(G ) is at most n/2, which by Eq. (1) is at most ( N o + N e + 1)/2 = (2N o + 1)/2 = N o = m. Now, assume that N e < N o . In this case, m = N e + 1 which is optimal by Theorem 3, completing the proof. 2 4. Conclusion and future work In this paper, we proved that the differential coloring problem is NP-hard for planar graphs and we presented tight upper bounds for regular caterpillars and spiders. We note that Rahaman et al. [22] independently obtain a result similar to our Theorem 2, i.e., an optimal labeling scheme for regular caterpillars. There are several natural open problems that we summarize below: – For general caterpillars, it is not known whether the maximum differential coloring problem can be solved in polynomial time or whether it is an NP-hard problem. – We proved that the maximum differential coloring is NP-complete even for planar graphs. It is worth mentioning that the computational complexity of the problem is not known for general trees and outer-planar graphs. – The decision version of the differential coloring problem is, given a graph G = ( V , E ) and a positive integer k ≤ | V |, determine whether G has differential chromatic number k. For general graphs the problem remains NP-complete even for k = 2. It is not known whether the problem remains NP-hard for planar graphs and fixed constant k. – Other open problems include finding optimal labeling schemes, NP-hardness results, and good approximations for other interesting graph classes, such as lobsters (trees in which removing all leaves results in a caterpillar), interval graphs, cubic graphs, and regular bipartite graphs. Acknowledgements We thank Jawaherul Alam, Aparna Das, Markus Geyer, Steven Chaplick and Sergey Pupyrev for many discussions about many different variants of the differential coloring problem.

M.A. Bekos et al. / Journal of Discrete Algorithms 29 (2014) 1–7

7

References [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29]

S. Assmann, G. Peck, M. Sysło, J. Zak, The bandwidth of caterpillars with hairs of length 1 and 2, SIAM J. Algebr. Discrete Methods 2 (4) (1981) 387–393. R. Bansal, K. Srivastava, Memetic algorithm for the antibandwidth maximization problem, J. Heuristics 17 (1) (2011) 39–60. T. Calamoneri, A. Massini, L. Török, I. Vrt’o, Antibandwidth of complete k-ary trees, Electron. Notes Discrete Math. 24 (2006) 259–266. S. Dobrev, R. Královic, D. Pardubská, L. Török, I. Vrt’o, Antibandwidth and cyclic antibandwidth of hamming graphs, Discrete Appl. Math. 161 (10–11) (2013) 1402–1408. A. Duarte, R. Martí, M. Resende, R. Silva, Grasp with path relinking heuristics for the antibandwidth problem, Networks 58 (3) (2011) 171–189. E.R. Gansner, Y.F. Hu, S.G. Kobourov, GMap: visualizing graphs and clusters as maps, in: IEEE Pacific Visualization Symposium (PacificVis 2010), 2010, pp. 201–208. M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979. P. Golovach, P. Heggernes, D. Kratsch, D. Lokshtanov, D. Meister, S. Saurabh, Bandwidth on AT-free graphs, Algorithms Comput. 412 (50) (2009) 573–582. A. Hajnal, E. Szemeredi, Proof of a conjecture of P. Erdös, Comb. Theory Appl. (1970) 601–623. W. Hale, Frequency assignment: theory and applications, Proc. IEEE 68 (12) (1980) 1497–1514. P. Heggernes, D. Kratsch, D. Meister, Bandwidth of bipartite permutation graphs in polynomial time, in: E. Laber, C. Bornstein, L. Nogueira, L. Faria (Eds.), LATIN 2008: Theoretical Informatics, in: Lect. Notes Comput. Sci., vol. 4957, Springer, Berlin, Heidelberg, 2008, pp. 216–227. Y. Hu, S. Kobourov, S. Veeramoni, On maximum differential graph coloring, in: U. Brandes, S. Cornelsen (Eds.), 18th International Symposium on Graph drawing (GD2010), in: Lect. Notes Comput. Sci., vol. 6502, Springer-Verlag, 2011, pp. 274–286. G. Isaak, Powers of Hamiltonian paths in interval graphs, J. Graph Theory 28 (1) (1998) 31–38. T. Kloks, D. Kratsch, H. Müller, Bandwidth of chain graphs, Inf. Process. Lett. 68 (6) (1998) 313–315. M. Kubale, Graph Colorings, Contemp. Math., vol. 352, American Mathematical Society, 2004. J.Y.-T. Leung, O. Vornberger, J.D. Witthoff, On some variants of the bandwidth minimization problem, SIAM J. Comput. 13 (3) (1984) 650–667. W.-Y. Lin, A.-C. Chu, Antibandwidth of bipartite graphs, in: 29th Workshop on Combinatorial Mathematics and Computation Theory, 2012, pp. 191–195. Y. Lin, A level structure approach on the bandwidth problem for special graphs, Ann. N.Y. Acad. Sci. 576 (1) (1989) 344–357. Z. Miller, D. Pritikin, On the separation number of a graph, Networks 19 (6) (1989) 651–666. B. Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete, SIAM J. Algebr. Discrete Methods 7 (4) (1986) 505–512. C. Papadimitriou, The NP-Completeness of the bandwidth minimization problem, Computing 16 (3) (1975) 263–270. M.S. Rahaman, T. Ahmed, S.A. Abdullah, M.S. Rahman, Antibandwidth problem for itchy caterpillar, in: 2014 International Conference on Informatics, Electronics Vision (ICIEV), May 2014, pp. 1–6. A. Raspaud, H. Schröder, O. Sýkora, L. Török, I. Vrt’o, Antibandwidth and cyclic antibandwidth of meshes and hypercubes, Discrete Math. 309 (11) (2009) 3541–3552. B. Reed, C. Linhares-Sales, Recent Advances in Algorithmic Combinatorics, Appl. Math. Sci., Springer, 2003. L. Török, I. Vrt’o, Antibandwidth of three-dimensional meshes, Discrete Math. 310 (3) (2010) 505–510. X. Wang, X. Wu, S. Dumitrescu, On explicit formulas for bandwidth and antibandwidth of hypercubes, Discrete Appl. Math. 157 (8) (2009) 1947–1952. Y. Weili, L. Xiaoxu, Z. Ju, Dual bandwidth of some special trees, J. Zhengzhou Univ. Nat. Sci. Ed. 35 (3) (2003) 16–19. J.-H. Yan, The bandwidth problem in cographs, Tamsui Oxford Univ. J. Math. Sci. 13 (1997) 31–36. L. Yixun, Y. Jinjiang, The dual bandwidth problem for graphs, J. Zhengzhou Univ. Nat. Sci. Ed. 35 (1) (2003) 1–5.