Printer Friendly

The inapproximability for the (0,1)-additive number.

An additive labeling of a graph G is a function l : V(G) [right arrow] N, such that for every two adjacent vertices v and u of G, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (x~y means that x is joined to y). The additive number of G, denoted by [eta](G), is the minimum number k such that G has a additive labeling l: V(G) [right arrow] [N.sub.k]. The additive choosability of a graph G, denoted by [[eta].sub.l](G), is the smallest number k such that G has an additive labeling for any assignment of lists of size k to the vertices of G, such that the label of each vertex belongs to its own list.

Seamone in his PhD thesis conjectured that for every graph G, [eta](G) = [[eta].sub.l](G). We give a negative answer to this conjecture and we show that for every k there is a graph G such that [[eta].sub.l](G) - [eta](G) [greater than or equal to] k.

A (0, 1)-additive labeling of a graph G is a function l : V(G) [right arrow] {0,1}, such that for every two adjacent vertices v and u of G, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. A graph may lack any (0,1)-additive labeling. We show that it is NP-complete to decide whether a (0,1)-additive labeling exists for some families of graphs such as perfect graphs and planar triangle-free graphs. For a graph G with some (0,1)-additive labelings, the (0,1)-additive number of G is defined as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [gamma] is the set of (0,1)-additive labelings of G. We prove that given a planar graph that admits a (0,1)-additive labeling, for all [epsilon] > 0, approximating the (0,1)-additive number within [n.sup.1-[epsilon]] is NP-hard.

Keywords: Additive labeling, additive number, lucky number, (0,1)-additive labeling, (0,1)-additive number, Computational complexity.

1 Introduction

Throughout the paper we denote {1, 2,..., k} by [N.sub.k]. An additive labeling of a graph G, which was introduced by Czerwinski et al. [11], is a function l: V(G) [right arrow] N, such that for every two adjacent vertices v and u of G, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](x ~ y means that x is joined to y). The additive number of G, denoted by [eta](G), is the minimum number k such that G has a additive labeling l: V(G) [right arrow] [N.sub.k]. Initially, additive labeling is called a lucky labeling of G. The following important conjecture was proposed by Czerwinski et al. [11].

Conjecture 1 [ Additive Coloring Conjecture [11]] For every graph G, [eta](G) [less than or equal to] [chi](G).

Czerwinski et al. also, considered the list version of above problem [11]. The additive choosability of a graph G, denoted by [[eta].sub.l](G), is the smallest number k such that G has an additive labeling from any assignment of lists of size k to the vertices of G. Idem above, about list-coloring proved that if T is a tree, then [[eta].sub.l](T) < 2, and if G is a bipartite planar graph, then [[eta].sub.l](G) [less than or equal to] 3 (for more information about the recent results see [9]). Seamone in his Ph.D dissertation posed the following conjecture about the relationship between additive number and additive choosability [23].

Conjecture 2 [Additive List Coloring Conjecture [23]] For every graph G, [eta](G) = [[eta].sub.l](G).

For a given connected graph G with at least two vertices, if no two adjacent vertices have a same degree, then [eta](G) = 1 and [[eta].sub.l](G) > 1. We show that not only there exists a counterexample for the above equality but also the difference between [eta](G) and [[eta].sub.l](G) can be arbitrary large.

Theorem 1 For every k there is a graph G such that [eta](G) [less than or equal to] k [less than or equal to] [[eta].sub.l](G)/2.

Chartrand et al. introduced another version of additive labeling and called it sigma coloring [10]. For a graph G, let c : V(G) [right arrow] N be a vertex labeling of G. If for every two adjacent vertices v and u of G, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then c is called a sigma coloring of G. The minimum number of labels required in a sigma coloring is called the sigma chromatic number of G and is denoted by [sigma](G). Chartrand et al. proved that, for every graph G, [sigma](G) [less than or equal to] [chi](G) [10]. Note that the only difference between additive labeling and sigma coloring is the objective function, but the feasible labelings are the same.

Additive labeling and sigma coloring have been studied extensively by several authors, for instance see [3, 4, 6, 8, 10, 11, 13, 21, 22]. It is proved, in [3] that it is NP-complete to determine whether a given graph G has [eta](G) = k for any k [greater than or equal to] 2. Also, it was shown that, it is NP-complete to decide for a given planar 3-colorable graph G, whether [eta](G) = 2 [3]. Furthermore, it was proved that, it is NP-complete to decide for a given 3-regular graph G, whether [eta](G) = 2 [13].

The edge version of additive labeling was introduced by Karonski, Luczak and Thomason [18]. They introduced an edge-labeling which is additive vertex-coloring that means for every edge uv, the sum of labels of the edges incident to u is different from the sum of labels of the edges incident to v [18]. It is conjectured that three integer labels [N.sub.3] are sufficient for every connected graph, except [K.sub.2] [18]. Currently the best bound is 5 [17]. This labeling has been studied extensively by several authors, for instance see [1, 2, 5, 14, 19, 20].

A clique in a graph G = (V, E) is a subset of its vertices such that every two vertices in the subset are connected by an edge. The clique number [omega](G) of a graph G is the number of vertices in a maximum clique in G. There is no direct relationship between the additive number and the clique number of graphs. For any natural number [omega] there exists a graph G, such that [omega](G) = [omega] and [eta](G) = 1. To see this for given number [omega], consider a graph G with the set of vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the set of edges [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 2 We have the following:

(i)For every graph G, [eta](G) [greater than or equal to] [w/[n-w+1]]

(ii) If G is a regular graph and [omega] > [[n+4]/3], then [eta](G) [greater than or equal to] 3.

A (0, 1)-additive labeling of a graph G is a function l : V(G) [right arrow] {0,1}, such that for every two adjacent vertices v and u of G, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. A graph may lack any (0, 1)-additive labeling. It was proved that, it is NP-complete to decide for a given 3-regular graph G, whether [eta](G) = 2 [13]. So, it is NP-complete to decide whether a (0, 1)-additive labeling exists for a given 3-regular graph G. In this paper, we study the computational complexity of (0, 1)-additive labeling for perfect graphs and planar graphs.

A graph G is called perfect if [omega](H) = [chi](H) for every induced subgraph H of G. Here, we show that it is NP-complete to decide whether a (0, 1)-additive labeling exists for perfect graphs.

Theorem 3 The following problem is NP -complete: Given a perfect graph G, does G have any (0,1)-additive labeling?

Next, we show that it is NP-complete to decide whether a (0, 1)-additive labeling exists for planar triangle-free graphs.

Theorem 4 It is NP-complete to determine whether a given planar triangle-free graph G has a (0,1)-additive labeling.

For a graph G with some (0, 1)-additive labelings, the (0, 1)-additive number of G is defined as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [GAMMA] is the set of (0, 1)-additive labelings of G. For a given graph G with a (0, 1)-additive labeling l the function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a proper vertex coloring, so we have the following trivial lower bound for [[sigma].sub.1](G).

[chi](G) - 1 [less than or equal to] [[sigma].sub.1](G).

We prove that given a planar graph that admits a (0, 1)-additive labeling, for all [epsilon] > 0, approximating the (0, 1)-additive number within [n.sup.1-[epsilon]] is NP-hard.

Theorem 5 If P [not equal to] NP, then for any constant [epsilon] > 0, there is no polynomial-time [n.sup.1-[epsilon]] -approximation algorithm for finding [[sigma].sub.1](G) for a given planar graph with at least one (0, 1)-additive labeling.

For v [member of] V(G) we denote by N(v) the set of neighbors of v in G. Also, for every v [member of] V(G), the degree of v is denoted by d(v). We follow [16, 24] for terminology and notation not defined here, and we consider finite undirected simple graphs G = (V, E).

2 Counterexample

Proof of Theorem 1: For every k we construct a graph G such that [[eta].sub.l](G) - [eta](G) [greater than or equal to] k. For every [alpha], [alpha] [N.sub.2k-1] consider a copy of complete graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with the vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Next, consider an isolated vertex t and join every vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to t, Call the resulting graph G. First, note that in every additive labeling l of G, for every (i, j), where i < j and i, j [member of] [N.sub.k] we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (because all the neighbors of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are common except [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as a neighbor of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and vice versa). Therefore [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are k distinct numbers, that means [eta](G) [greater than or equal to] k. Define (for every [alpha] and [beta]):

l : V(G) [right arrow] [N.sub.k], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

l(t) = k.

It is easy to see that l is an additive labeling for G. Next, we show that [[eta].sub.l](G) > 2k-1. Consider the following lists for the vertices of G (for every [alpha] and [beta]).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

L(t) = [N.sub.2k-1].

To the contrary suppose that [[eta].sub.l](G) [less than or equal to] 2k - 1 and let t be an additive labeling from the above lists. Suppose that l(t) = r. Consider the complete graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for every [beta] we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, consider the following partition for [N.sub.2k-1] [union] {i + r : i [member of] [N.sub.2k-1]},

{1 + r, 1}, {2 + r, 2},..., {2k - 1 + r,2k - 1}.

By Pigeonhole Principle, there are indices i, n and m such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], so [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This is a contradiction, so [[eta].sub.l](G) [greater than or equal to] 2k. []

3 Lower bounds

Proof of Theorem 2: (i) Let l : V(G) [right arrow] [N.sub.k] be an additive labeling of G and suppose that T = {[v.sub.i]|i [member of] [N.sub.[omega]] } is a maximum clique in G. For each vertex v [member of] T, define the function [Y.sub.v].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For every two adjacent vertices v and u in T, we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, [Y.sub.v1],..., [Y.sub.v[omega]] are distinct numbers. On the other hand, for each vertex v [member of] T, the image of the function [Y.sub.v] is [-k, k(n - w) - 1]. So w [less than or equal to] k(n - w + 1), therefore k [greater than or equal to] [[w]/n-w+1] and the proof is completed.

(ii) Let G be a regular graph, obviously [eta](G) [greater than or equal to] 2. To the contrary suppose that [eta](G) = 2. Let T be a maximum clique in G and c : V(G) [right arrow] {1, 2} be an additive labeling of G. Define:

[X.sub.1] = [c.sup.-1](1) [intersection] T, [X.sub.2] = [c.sup.-1](2) [intersection] T, [Y.sub.1] = [c.sup.-1](1) \T, [Y.sub.2] = [c.sup.-1](2) \ T.

Suppose that [X.sub.1] = {[v.sub.1],... , [v.sub.k]} and [X.sub.2] = {[v.sub.k+1],... , [v.sub.[omega]]}. For each i [member of] [N.sub.[omega]], denote the number of neighbors of [v.sub.i], in [Y.sub.1] by [d.sub.i]. Since c is an additive labeling of the regular graph, every two adjacent vertices have different numbers of neighbors in [c.sup.-1](1). Therefore [d.sub.1],..., [d.sub.k], 1 + [d.sub.k+1],... ,1 + [d.sub.[omega]] are distinct numbers. Since for each i [member of] [N.sub.[omega]], 0 [less than or equal to] di [less than or equal to] |[Y.sub.1]|, we have |[Y.sub.1]| > [omega] - 2. Similarly, |[Y.sub.2]| > [omega] - 2, n = |T| + |[Y.sub.1]| + |[Y.sub.2]| [greater than or equal to] 3[omega] - 4.

This is a contradiction. So the proof is completed. []

4 List Coloring Problem

Proof of Theorem 3: Let G be a graph and let L be a function which assigns to each vertex v of G a set L(v) of positive integers, called the list of v. A proper vertex coloring c : V(G) [right arrow] N such that f(v) [member of] L(v) for all v [member of] V is called a list coloring of G with respect to L, or an L-coloring, and we say that G is L-colorable.

Next, for a given graph G and a list L(v) for every vertex v, we construct a graph [H.sub.G] such that [H.sub.G] has a (0, 1)-additive labeling if and only if G is L-colorable.

Define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let f be a bijective function from the set W to the set [N.sub.|W| + 1] {1}. For every vertex v [member of] V(G), let [L.sub.f] (v) = {f(i) |i [member of] L(v)}. The graph G is L-colorable if and only if G is [L.sub.f] -colorable. Now, we construct [H.sub.G] form G and [L.sub.f].

Construction of [H.sub.G].

We use three auxiliary graphs T(w), I(j) and G(v, [L.sub.f](v), s). The gadgets I(j) and T(w) are shown in Figure 1. Consider a vertex v and a copy of auxiliary graph T(w). Join the vertex v to T(w). Next, for every j[member of] ([N.sub.s]\{1})|[L.sub.f](v) consider a copy of I(j) and join the vertex v to the vertex [u.sub.j]. Finally, put s isolated vertices and join each of them to the vertex v. Call the resulting graph G(v, [L.sub.f](v), s). Now, for every vertex v [member of] V(G) put a copy of G(v, [L.sub.f](v), |W + 1) and for every edge vv' in the graph G join the vertex v [member of] V(G(v, [L.sub.f](v), |W| + 1)) to the vertex v | [member of] V(G(v', [L.sub.f](v'), |W| + 1)). Call the resulting graph [H.sub.G].

For a family F of graphs, define: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We show that if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a family of graphs such that list coloring problem is NP-complete for that family. Then, the following problem is NP-complete: "Given a graph [H.sub.G] [member of] F', does HG have a (0, 1)-additive labeling?"

[FIGURE 1 OMITTED]

First consider the following facts.

Fact 1 Let G be a graph with a (0, 1)-additive labeling l and assume that it has the auxiliary graph T(w) as a subgraph, l(v) = 0, l(w) = 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof of Fact 1. By attention to the two triangles [x.sub.1][x.sub.2][x.sub.3] and [y.sub.1][y.sub.2][y.sub.3], l(w) = 1 and l([y.sub.4]) = 1. Also l([x.sub.1]) [not equal to] t([x.sub.2]), without loss of generality suppose that l([x.sub.1]) = 1 and l([x.sub.2]) = 0. Therefore, l([x.sub.3]) = 0, thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], therefore [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], consequently l(v) = 0.

Fact 2 Let G be a graph with a (0, 1)-additive labeling t and assume that it has the auxiliary graph I(j) as a subgraph, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof of Fact 2. By Fact 1, l(w) = 1, by using a similar argument i([z.sub.1]) =... = l([z.sub.j-1]) = 1. So [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Fact 3 Let l be a (0, 1)-additive labeling for G(v, [L.sub.f](v), |W| + 1), [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof of Fact 3. By Fact 1 and Fact 2 it is clear.

First, suppose that the graph HG has a (0, 1)-additive labeling l, define c : V(G) [right arrow] N, c(v) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The function cis a proper vertex coloring and for every vertex v, by Fact 3, c(v) [member] [L.sub.f](v). Next, suppose that the graph G is [L.sub.f]-colorable, then it is clear that the graph [H.sub.G] has a (0, 1)-additive labeling.

The list coloring problem is NP-complete for perfect graphs and planar graphs (see [7]). Obviously if G is a planar graph, then [H.sub.G] is a planar graph. Also, if G is a perfect graph, then it is easy to see that the graph [H.sub.G] is a perfect graph. This completes the proof. []

5 Planar graphs

Proof of Theorem 4: Let [PHI] be a 3-SAT formula with the set of clauses C and the set of variables X. Let G([PHI]) be a graph with the vertices C [union] X [union] ([logical not]X), where [logical not]X = {[logical not]x : x [member of] X}, such that for each clause c = y [disjunction] z [disjunction] w, cis adjacent to y, z and w, also every x [member of] X is adjacent to [logical not]x. [PHI] is called planar 3-SAT(type 2) formula if G([PHI]) is a planar graph. It was shown that the problem of satisfiability of planar 3-SAT(type 2) is NP-complete [15]. In order to prove our theorem, we reduce the following problem to our problem.

Problem: Planar 3-SAT(type 2).

INPUT: A planar 3-SAT(type 2) formula [PHI].

QUESTION: Is there a truth assignment for [PHI] that satisfies all the clauses?

Consider an instance of planar 3-SAT(type 2) with the set of variables X and the set of clauses C. We transform this into a graph G'([PHI]) such that G'([PHI]) has a (0, 1)-additive labeling, if and only if [PHI] is satisfiable. The graph G'([PHI]) has a copy of B (x) for each variable x and a copy of A(c) for each clause c. The gadgets B(x) and A(c) are shown in Figure 2. Also, for every c [member of] C, x [member of] X, the edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is added if c contains the literal x. Furthermore, for every c [member of] C, [logical not]x [member of] [logical not]X, the edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is added if c contains the literal [logical not]x. Call the resulting graph G'([PHI]). Clearly the graph G'([PHI]) is triangle-free and planar.

[FIGURE 2 OMITTED]

Fact 4 Let l be a (0, 1)-additive labeling for the graph G'([PHI]), for each clause c = a [disjunction] b [disjunction] d, l(a) + l(b) + l(d) [greater than or equal to] 1.

Proof of Fact 4. To the contrary suppose that there exists a clause c = a [disjunction] b [disjunction] d, such that l(a)+ l(b) + l(d) = 0, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Notice that in that case, l restricted to the odd cycle [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is a (0,1)-additive labeling, but an odd cycle does not have any (0, 1)-additive labeling, this is a contradiction.

Fact 5 Let G'([PHI]) be a graph with a (0, 1)-additive labeling l, for each variable x, l(x) + l([logical not]x) [less than or equal to] 1.

Proof of Fact 5. To the contrary, suppose that there is a variable x, such that l(x) + l([logical not]x) = 2. Consider the auxiliary graph B(x). Because of the odd cycle [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now two cases for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be considered.

Case 1. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], therefore [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

* If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; without loss of generality suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], in this case [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], but this is a contradiction.

* If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Four subcases for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be considered, each of them produces a contradiction.

Case 2. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], therefore [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

* If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. With no loss of generality suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], therefore [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], but this is a contradiction.

* If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], therefore [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], this is a contradiction.

First, suppose that [PHI] is satisfiable with the satisfying assignment [GAMMA] : X [right arrow] {true, false}. We present a (0, 1)-additive labeling t for G'([PHI]). For every variable x if [GAMMA](x) = true, then put l(x) = 1, otherwise put l([logical not]x) = 1. Also put [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover, for every clause c, put [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is easy to extend this labeling to a (0, 1)-additive labeling for the graph G'([PHI]). Next, suppose that the graph G'([PHI]) has a (0, 1)-additive labeling l. For each variable x, by Fact 5, l(x) +l([logical not]x) [less than or equal to] 1. If l(x) = 1, put [GAMMA](x) = true, if l([logical not]x) = 1, then put [GAMMA](x) = false and otherwise put [GAMMA](x) = true. By Fact 4, [GAMMA] is a satisfying assignment for [PHI]. []

6 Inapproximability

Proof of Theorem 5: Let [epsilon] > 0 and k be a sufficiently large number. It was shown that 3-colorability of 4-regular planar graphs is NP-complete [12]. We reduce this problem to our problem. In other words, for a given 4-regular planar graph G with k vertices, we construct a planar graph G* with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] vertices, such that if [chi](G) [less than or equal to] 3, then [[sigma].sub.1](G*) [less than or equal to] 5k, otherwise [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], therefore there is no [theta]-approximation algorithm for determining [[sigma].sub.1](G*) for planar graphs, where:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In order to construct the graph G*, we use the auxiliary graph D(v) which is shown in Figure 3. Using simple local replacements, for every vertex v of the graph G, put a copy of D(v), and for every edge vu of the graph G, join the vertex v of D(v) to the vertex u of D(u). Call the resulting graph G*. First, suppose that G is not 3-colorable and let l be a (0, 1)-additive labeling for G*. By the structure of D(v) we have l(v) = 1 and l(p3) = 0, so [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since G is not 3-colorable, there exists a vertex v such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], therefore in the subgraph D(v), l([p.sub.4]) + l([p.sub.5]) + l([p.sub.6]) = 0, so l([p.sub.5]) = 0. Consequently for every i, 1 [less than or equal to] i [less than or equal to] d, in the subgraph D(v), l([v.sub.i]) + l([v'.sub.i]) [greater than or equal to] 1. So [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Next, suppose that [chi](G) [less than or equal to] 3. So G has a proper vertex coloring c : V(G) [right arrow] {1,2,3}. For every vertex v of G, if c(v) = 1 put l([p.sub.4]) = t([p.sub.6]) = 0 and l([p.sub.5]) = 1, else if c(v) = 2 let l([p.sub.4]) = 0 and l([p.sub.5]) = l([p.sub.6]) = 1 and if c(v) = 3 let l([p.sub.4]) = l([p.sub.5]) = l([p.sub.6]) = 1. It is easy to extend l to a (0, 1)-additive labeling for the graph G* such that [[sigma].sub.1](G*) [less than or equal to] 5k. []

7 Concluding remarks

In this paper we study the computational complexity of (0, 1)-additive labeling of graphs. A (0,1)-additive labeling of a graph G is a function l : V(G) [right arrow] {0,1}, such that for every two adjacent vertices v and u of G, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For future work, someone can consider another version of this problem that we call proper total dominating set. A proper total dominating set of a graph G = (V, E), is a subset D of V such that every vertex has a neighbor in D (all vertices in the graph including the vertices in the dominating set have at least one neighbor in the dominating set) and every two adjacent vertices have a different number of neighbors in D (note that in a (0,1)-additive labeling every vertex does not need to have a neighbor labeled 1).

In this work, we proved that for every k there is a graph G such that [eta](G) [less than or equal to] k [less than or equal to] [[eta].sub.l](G)/2. What can we say about the difference in bipartite graphs?

[FIGURE 3 OMITTED]

Acknowledgements

The authors wish to thank Saieed Akbari who drew their attention to Additive List Coloring Conjecture.

References

[1] L. Addario-Berry, R. E. L. Aldred, K. Dalal, and B. A. Reed. Vertex colouring edge partitions. J. Combin. Theory Ser. B, 94(2):237-244, 2005.

[2] L. Addario-Berry, K. Dalal, and B. A. Reed. Degree constrained subgraphs. Discrete Appl. Math., 156(7):1168-1174, 2008.

[3] A. Ahadi, A. Dehghan, M. Kazemi, and E. Mollaahmadi. Computation of lucky number of planar graphs is NP-hard. Inform. Process. Lett., 112:109-112, 2012.

[4] S. Akbari, M. Ghanbari, R. Manaviyat, and S. Zare. On the lucky choice number of graphs. Graphs Combin., 29(2):157-163, 2013.

[5] T. Bartnicki, J. Grytczuk, and S. Niwczyk. Weight choosability of graphs. J. Graph Theory, 60(3):242-256, 2009.

[6] Tomasz Bartnicki, BartLomiej Bosek, Sebastian Czerwinski, JarosLaw Grytczuk, Grzegorz Matecki, and Wiktor Zelazny. Additive coloring of planar graphs. Graphs and Combinatorics, 30(5):1087-1098, 2014.

[7] F. Bonomo, G. Duran, and J. Marenco. Exploring the complexity boundary between coloring and list--coloring. Electronic Notes in Discrete Mathematics, 25:41-47, 2006.

[8] M. Borowiecki, J. Grytczuk, and M Pilsniak. Coloring chip configurations on graphs and digraphs. Inform. Process. Lett., 112(1-2):1-4, 2012.

[9] Axel Brandt, Jennifer Diemunsch, and Sogol Jahanbekam. Lucky choice number of planar graphs with given girth. Submitted, 2015.

[10] Gary Chartrand, Futaba Okamoto, and Ping Zhang. The sigma chromatic number of a graph. Graphs Combin., 26(6):755-773, 2010.

[11] Sebastian Czerwinski, JarosLaw Grytczuk, and Wiktor Zelazny. Lucky labelings of graphs. Inform. Process. Lett., 109(18):1078-1081, 2009.

[12] David P. Dailey. Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discrete Math., 30(3):289-293, 1980.

[13] A. Dehghan, M.-R. Sadeghi, and A. Ahadi. The complexity of the sigma chromatic number of cubic graphs. Submitted.

[14] Ali Dehghan, Mohammad-Reza Sadeghi, and Arash Ahadi. Algorithmic complexity of proper labeling problems. Theoretical Computer Science, 495:25-36, 2013.

[15] Ding-Zhu Du, Ker-K Ko, and J. Wang. Introduction to Computational Complexity. Higher Education Press, 2002.

[16] M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. Bull. Amer. Math. Soc. (N.S.), 3(2):898-904, 1980.

[17] Maciej Kalkowski, MichaL Karonski, and Florian Pfender. Vertex-coloring edge-weightings: towards the 1-2-3-conjecture. J. Combin. Theory Ser. B, 100(3):347-349, 2010.

[18] MichaL Karonski, Tomasz Luczak, and Andrew Thomason. Edge weights and vertex colours. J. Combin. Theory Ser. B, 91(1):151-157, 2004.

[19] M. Khatirinejad, R. Naserasr, M. Newman, B. Seamone, and B Stevens. Digraphs are 2-weight choosable. Electron. J. Combin., 18(1):Paper 21,4, 2011.

[20] M. Khatirinejad, R. Naserasr, M. Newman, B. Seamone, and B. Stevens. Vertex-colouring edgeweightings with two edge weights. Discrete Math. Theor. Comput. Sci., 14(1):1-20, 2012.

[21] MichaL Lason. A generalization of combinatorial Nullstellensatz. Electron. J. Combin., 17(1):Note 32, 6, 2010.

[22] Javier Marenco, Marcelo Mydlarz, and Daniel Severin. Topological additive numbering of directed acyclic graphs. Information Processing Letters, 115(2):199-202, 2015.

[23] B. Seamone. Derived colourings of graphs. PhD thesis, Carleton University, 2012.

[24] Douglas B. West. Introduction to graph theory. Prentice Hall Inc., Upper Saddle River, NJ, 1996.

Arash Ahadi (1) Ali Dehghan (2*)

(1) Sharif University of Technology, Tehran, Iran

(2) Carleton University, Ottawa, Ontario, Canada

received 27th Apr. 2013, revised 15th Apr. 2016, accepted 8th June 2016.

(*) Corresponding author.

E-mail Addresses: arash-ahadi@mehr.sharif.edu (Arash Ahadi) alidehghan@sce.carleton.ca (Ali Dehghan).
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Ahadi, Arash; Dehghan, Ali
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:5252
Previous Article:The irregularity of two types of trees.
Next Article:On the complexity of edge-colored subgraph partitioning problems in network optimization.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters