A Generalized Coloring of Graphs

Ashok Amin Department of Computer Science University of Alabama in Huntsville Huntsville, AL 35899-0001

Lane Clark Department of Mathematics Southern Illinois University at Carbondale Carbondale, IL 62901-4408

John McSorley Department of Mathematical Sciences Michigan Technological University Houghton, MI 49931-1295

Hui Wang Department of Computer Science University of Alabama in Huntsville Huntsville, AL 35899-0001

Grant Zhang Department of Mathematical Sciences University of Alabama in Huntsville Huntsville, AL 35899-0001

Abstract. Let χ^{∗}(G) denote the minimum number of colors required in a coloring c of the vertices of G where for adjacent vertices u,v we have c(N_{G}[u])≠c(N_{G}[v]) when N_{G}[u]≠N_{G}[v] and c(u)≠c(v) when N_{G}[u]=N_{G}[v]. We show that the problem of deciding whether χ^{∗}(G)≤n, where n≥3, is NP-complete for arbitrary graphs. We find χ^{∗}(G) for several classes of graphs including bipartite graphs, complete multipartite graphs, as well as, cycles and their complements. A sharp lower bound is given for χ^{∗}(G) in terms of χ(G) and an upper bound is given for χ^{∗}(G) in terms of Δ(G). For regular graphs with girth at least four we give substantially better upper bounds for χ^{∗}(G) using random colorings of the vertices.

1. Introduction.

Addressing scheme used for electronic mail is hierarchical, and is represented by a tree. An individual, who belongs to more than one organization or group, may have more than one address called aliases. This can be modeled by an acyclic directed graph. On the other hand, two different individuals belonging to the same organization and with the same initial and last name may have the same address. In such a case, address resolution may be based on the set of aliases associated with each individual provided that these sets are distinct. In the context of generalized graph coloring, each vertex is to be distinguished from its neighbors based on the name or color assigned to it. Therefore, we require that if two adjacent vertices have the same closed neighborhood, then their colors be distinct; otherwise, it is enough to require that the set of colors assigned to the closed neighborhood of each vertex be distinct. Our discussion motivates the following definition.

For a graph G, a (not necessarily proper) coloring c of the vertices of G is a good coloring of G if and only if for all edges uv of G, c(u) ≠ c(v) when N_{G}[u] = N_{G}[v] and c(N_{G}[u]) ≠ c(N_{G}[v]) when N_{G}[u] ≠ N_{G}[v]. A good coloring of G using k colors will be referred to as a good k-coloring of G. If we assign each vertex of G a different color we have a good coloring of G. Let χ^{∗}(G) denote the minimum number of colors required in a good coloring of G. Hence, χ^{∗}(G) ≤ n when G has order n. It is readily seen that χ^{∗}(G) ≥ 3 for any connected graph G with order at least 3.

A simple graph G has vertex set V (G) and edge set E(G). The order of G is |V (G)| and the size of G is |E(G)|. For a vertex v in G, the open neighborhood N_{G}(v) of v in G is the set of all vertices in G adjacent to v and the closed neighborhood N_{G}[v] = N_{G}(v) ∪ {v}. The degree d_{G}(v) of a vertex v in G is |N_{G}(v)| and Δ(G) is the maximum degree of a vertex in G. For vertices u, v in G, the distance d_{G}(u, v) between u, v in G is the length of a shortest (u, v)-path in G. We denote a cycle (path) of order n by C_{n} (P_{n}) and the complement of a graph G by \overline{G}. The girth of G is the length of a shortest cycle in G. All other notation and terminology generally follows Bondy and Murty [1]. Unless otherwise noted, all logarithms are natural.

2. Complexity.

We show that the problem of deciding whether χ^{∗}(G) ≤ n, where n ≥ 3, is NP-complete for arbitrary graphs.

Graph n-Colorability INSTANCE: Graph G = (V, E). QUESTION: Is G n-colorable, i.e., does there exist a function c : V → {1, …, n} such that c(u) ≠ c(v) whenever {u, v} ∈ E?

It is known that graph n-colorability, for n ≥ 3, is NP-Complete. (see [4].)

Graph Generalized n-Colorability INSTANCE: Graph G = (V, E). QUESTION: Does G have a good n-coloring?

Theorem 1. Graph generalized n-colorability for any n ≥ 3 is NP-Complete.

Proof. Clearly, graph generalized n-colorability is in NP. Consider the reduction from the graph n-colorability problem. Let G = (V, E) be a given graph. Construct graph G′ = (V′, E′) as follows. Replace each edge uv ∈ E by P_{4} = u, u′, v′, v where u′, v′ are new vertices, and replace each vertex u ∈ V by C_{4} = u, u_{1}, u_{2}, u_{3}, u, where u_{1}, u_{2}, u_{3} are new vertices.

Let c_{1} be a proper n-coloring of G. We show that c_{1} induces a good n-coloring c_{2} of G′. For each {u, v} ∈ E, if c_{1}(u) = i and c_{1}(v) = j then c_{2}(u) = i, c_{2}(v) = j, and c_{2}(u′) = c_{2}(v′) = k where k is any color other than i, j. For each u ∈ V if c_{1}(u) = i then c_{2}(u) = i, c_{2}(u_{1}) = j, c_{2}(u_{2}) = i, and c_{2}(u_{3}) = k where j, k are distinct colors different than i. It is easily verfied that c_{2} is a good n-coloring of G′.

Conversely, let c_{2} be a good n-coloring of G′. Consider edge uv ∈ E and let P_{4} = u, u′, v′, v be the corresponding path in G′. If c_{2}(u) = c_{2}(v) then c_{2}(N_{G′}[u′]) = c_{2}(N_{G′}[v′]), hence, c_{2}(u) ≠ c_{2}(v). Therefore, by setting c_{1}(u) = c_{2}(u) for each u ∈ V, we obtain a proper n-coloring of G. ■ As our construction preserves planarity, graph generalized n-colorability, for any n ≥ 3, is NP-complete for planar graphs.

3. Exact Values.

In this section we find χ^{∗}(G) for several classes of graphs.

Theorem 2. For a connected bipartite graph G with order at least 3,

χ^{∗}(G) = 3.

Proof. Let v be a vertex of G whose eccentricity is r = radius(G) ≥ 2 (r = 1 being trivial). Let N^{k} = N^{k}(v) = {w ∈ V (G) : d_{G}(v, w) = k}, O^{k} = O^{k}(v) = {w ∈ N^{k}(v) : N_{G}(w) ⊆ N^{k−1}} and P^{k} = P^{k}(v) = N^{k}(v) − O^{k}(v) for 0 ≤ k ≤ r. Each set N^{k} is independent since G is bipartite. Now color N^{4k} color 1; N^{4k+2} color 3; O^{4k+1} color 1; P^{4k+1} color 2; O^{4k+3} color 3, and P^{4k+3} color 2. It is easily seen that this is a good 3-coloring of G so that χ^{∗}(G) = 3. ■

Theorem 3. We have

χ^{∗}(C_{n}) = \{ \begin{matrix}4 & , n = 5 or 7 \\ 3 & , n is odd and n ≥ 9. \end{matrix}

Proof. It is easy to verify the result for n = 5 or 7. So we assume n ≥ 9. It is sufficient to construct a good coloring c of C_{n} using three colors. Let C_{n} = v_{0}, v_{1}, …, v_{n−1}, v_{0}. We define the good 3-coloring c of C_{n} as follows.

c(v_{i}) = \{ \begin{matrix}1 & , i is even \\ 2 & , i ≡ 1 (mod 4) \\ 3 & , i ≡ 3 (mod 4) \end{matrix}

with the exceptions that c(v_{2}) = 3, and c(v_{n−3}) = 2 when n ≡ 1 (mod 4); c(v_{0}) = 2, and c(v_{1}) = c(v_{2}) = c(v_{n−3}) = 3 when n ≡ 3 (mod 4). ■

Theorem 4. If G is a complete t-partite graph with exactly m vertices of degree |V (G)|−1, then

χ^{∗}(G) = \{ \begin{matrix}2t − 1 & , m = 0 \\ 2t − m & , m > 0. \end{matrix}

Proof. Let P_{1}, P_{2}, …, P_{t} be the t-partitions of V (G) such that |P_{i}| = 1 if and only if 1 ≤ i ≤ m. Let c be a good coloring of G using χ^{∗}(G) colors. Define C_{i} = c(P_{i}) for 1 ≤ i ≤ m, and C_{i} = c(P_{i}) − c(V (G) − P_{i}) for m < i ≤ t. Then we can easily check the following three observations.

(i) C_{i} ∩ C_{j} = ∅ whenever i ≠ j. (ii) If m < i ≠ j ≤ t, then either |C_{i}| > 1 or |C_{j}| > 1. (iii) If |C_{i}| ≤ 1 for some i > m, then m = 0. We now consider two cases.

Case 1. m = 0.

In this case we may assume |C_{i}| > 1 for all i > 1 by (ii) and (iii). Note that C_{1} ∩ C_{j} = ∅ for all j > 1. Then we have χ^{∗}(G) ≥ |C_{1}| + ∑_{i=2}^{t} |C_{i}| ≥ 1 + 2(t − 1) = 2t − 1.

Case 2. m > 0.

In this case we have |C_{i}| > 1 for all i > m. Then χ^{∗}(G) ≥ ∑_{i=1}^{t} |C_{i}| ≥ m + 2(t − m) = 2t − m.

This proves the lower bound.

Now let c be a good coloring of G such that (i) C_{i} ∩ C_{j} = ∅ whenever 1 ≤ i ≠ j ≤ t; and (ii) |C_{i}| = 2 whenever i > m with the exception that |C_{1}| = 1 if m = 0. Then clearly c is a good coloring of G. ■

Lemma 5. Let V be a finite set, and S = {B_{1}, B_{2}, …, B_{b}} be a collection of distinct subsets of V such that

(i) 1 ≤ |B_{i}| ≤ 2 for each i; (ii) 1 ≤ r_{v} ≤ 2 for each v ∈ V, where r_{v} denotes the number of subsets in S containing v. Then |V | ≥ (2b + a_{1})/3, where a_{1} denotes the number of v’s so that r_{v} = 1.

Proof. For i = 1, 2, let a_{i} denote the number of v’s in V so that r_{v} = i and b_{i} denote the number of subsets of size i in S. By counting the number of ordered pairs (v, B_{i}), where v ∈ B_{i} ⊆ V, in two ways we have

2a_{2} + a_{1} = 2b_{2} + b_{1}.  (1)

Now let τ be the number of ordered pairs (v, B_{i}) such that v ∈ B_{i}, |B_{i}| = 2, and r_{v} = 2. Then we have a_{2} ≤ τ ≤ 2b_{2} or b_{2} ≥ \frac{1}{2}a_{2}. This, together with (1), implies that 2a_{2} + a_{1} ≥ b + a_{2}/2, or

3|V | = 3(a_{1} + a_{2}) ≥ 2b + a_{1}.

Then |V | ≥ (2b + a_{1})/3. ■

Theorem 6. We have

χ^{∗}(\overline{C}_{n}) = \{ \begin{matrix}⌈(2n + 2)/3⌉ & , n ≡ 0, 5 (mod 6), n ≠ 12 \\ ⌈(2n − 1)/3⌉ & , n ≢ 0, 5 (mod 6) \\ 8 & , n = 12. \end{matrix}

Proof. We first prove the lower bound. Assume V (\overline{C}_{n}) = \{v_{1}, v_{2}, …, v_{n}\} such that v_{i}v_{j} ∈ E(\overline{C}_{n}) if and only if i and j are not consecutive, i.e., j ≢ i + 1 (mod n). Let c be a good coloring of \overline{C}_{n} with the color set X = \{x_{1}, x_{2}, …, x_{t}\}, where t = χ^{∗}(\overline{C}_{n}). Define B_{i} = X − c(N_{\overline{C}_{n}}(v_{i})) for 1 ≤ i ≤ n. Clearly B_{i} = ∅ for at most two i’s, in which case they are consecutive. Hence, we assume B_{i} ≠ ∅ if and only if 1 ≤ i ≤ b, where n − 2 ≤ b ≤ n, and let S = {B_{1}, B_{2}, …, B_{b}}. It can be seen that all the sets in S are distinct. Now let r_{x} denote the number of B_{i} in S containing x for every x ∈ X. Thus r_{x} ≤ 2 for all x ∈ X. We then define A_{i} = {x_{j} : r_{x_{j}} = i} and a_{i} = |A_{i}| for 0 ≤ i ≤ 2. Therefore, χ^{∗}(\overline{C}_{n}) = t = a_{0} + a_{1} + a_{2}.

Case 1. a_{0} > 0.

Define S_{1} = {B_{1}, B_{3}, …, B_{α}}, S_{2} = {B_{2}, B_{4}, …, B_{β}}, X_{1} = B_{1} ∪ B_{3} ∪ ⋯ ∪ B_{α}, X_{2} = B_{2} ∪ B_{4} ∪ ⋯ ∪ B_{β}, where α = 2⌈n/2⌉ − 3 and β = 2⌊n/2⌋ − 2. Then we have X_{1} ∩ X_{2} = ∅, and we can apply Lemma 5 to both (X_{1}, S_{1}) and (X_{2}, S_{2}), so that

|X_{1}| ≥ \frac{2}{3} (\frac{α + 1}{2}) and |X_{2}| ≥ \frac{2}{3} (\frac{β}{2} ) .

Thus

χ^{∗}(\overline{C}_{n}) = t = |X_{1}| + |X_{2}| + a_{0} ≥ ⌈\frac{α + 1}{3}⌉ + ⌈\frac{β}{3} ⌉ + 1

= ⌈\frac{2}{3}(⌈n/2⌉ − 1)⌉ + ⌈\frac{2}{3}(⌊n/2⌋ − 1)⌉ + 1,

which is at least as large as the lower bound.

Case 2. a_{0} = 0.

In this case we can apply Lemma 5 to (X, S) so that

χ^{∗}(\overline{C}_{n}) = t ≥ \frac{2b + a_{1}}{3} = \frac{2n + a_{1} − 2(n − b)}{3}  (2)

If B_{n} = ∅, then we have c(v_{n−1}) ≠ c(v_{1}), for otherwise c(v_{1}) would be a color in A_{0}. Furthermore, we have c(v_{n−1}) and c(v_{1}) are both contained in A_{1}. Similarly, if B_{n} = B_{n−1} = ∅, we can check that c(v_{n−2}), c(v_{n−1}), c(v_{n}), and c(v_{1}) are distinct and contained in A_{1}. Thus we have shown that a_{1} ≥ 2(n − b). Therefore, by (2), we may assume

a_{1} = 2(n − b) ≤ 4  (3)

Hence, χ^{∗}(\overline{C}_{n}) ≥ \frac{2n}{3} and we may asssume n ≡ 0 (mod 6) with n ≠ 6.

Notice that each color in A_{2} (A_{1}) is used exactly once (twice) in V (\overline{C}_{n}). Then we have 2a_{1} + a_{n} = n, and (3) implies that

χ^{∗}(\overline{C}_{n}) = a_{1} + a_{2} = n − a_{1} ≥ n − 4,

which is at least as large as the lower bound unless n ≤ 11.

This completes the proof of the lower bound.

We now prove the upper bound. The graph in Figure 1 covers the case n = 12, where the number next to each vertex represents the color of that vertex.

Figure 1.  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}• • • • • • • • • • • • 3 4 3 1 2 1 2 8 7  6  5 4

Write n = 6m + r, where 1 ≤ r ≤ 6. Define R = ∅ if r ≤ 2; R = {x_{i} : 1 ≤ i ≤ r − 2} if r ≥ 3; and S = {0} ∪ {a_{i}, b_{i}, c_{i}, d_{i} : 0 ≤ i ≤ m − 1}. We now define a good coloring c of G using colors in S ∪ R as follows.

(i) For k = 6j + i, where 0 ≤ j ≤ m − 1, and 1 ≤ i ≤ 6,

c(v_{k}) = \{ \begin{matrix}0 & , 1 ≤ i ≤ 2 \\ a_{j} & , i = 3 \\ b_{j} & , i = 4 \\ c_{j} & , i = 5 \\ d_{j} & , i = 6. \end{matrix}

(ii) c(v_{n}) = 0 if r = 1 (iii) For r ≥ 2, k = 6m + i, where 1 ≤ i ≤ r,

c(v_{k}) = \{ \begin{matrix}x_{i} & , 1 ≤ i ≤ r − 2 \\ 0 & , i = r − 1 or r. \end{matrix}

It is easily seen that c is a good coloring of \overline{C}_{n}. ■

Definition. We say a vertex v distinguishes an edge e = xy in G if and only if (N_{G}[x] − N_{G}[y]) ∪ (N_{G}[y] − N_{G}[x]) = {v}.

Lemma 7. For any graph G, there exists a vertex v in G that does not distinguish any edge of G.

Proof. Suppose not. Let V (G) = {v_{1}, …, v_{n}} where v_{i} distinguishes the edge e_{i} for 1 ≤ i ≤ n. Let H denote the subgraph of G induced by the n edges {e_{i} : 1 ≤ i ≤ n}. Then H contains exactly n edges and at most n vertices. Then H contains a cycle C = w_{0}, w_{1}, …, w_{r−1}, w_{0}. Without loss of generality, we may assume e_{i} = w_{i−1}w_{i} for 1 ≤ i ≤ r. Now for any 1 ≤ i ≠ j ≤ r, v_{i} is adjacent to exactly one of w_{i−1} and w_{i}, and v_{i} is adjacent to neither or both of w_{j−1} and w_{j}. Hence, if v_{i}w_{i} ∈ E(G), then v_{i} would be adjacent to all the other vertices in C, which is impossible. ■

Given any graph G, we use s(G) to denote the maximum number of vertices in G all having the same closed neighborhood. Then we have s(G) ≤ |V (G)|, with equality if and only if G is a complete graph.

Theorem 8. Let H be a graph of order n and K_{n} be vertex-disjoint from H, where n ≥ 2. Define G to be the graph obtained from H and K_{n} by adjoining a 1-factor between H and K_{n}. Then we have χ^{∗}(G) = n − 1 + s(H), unless each component of H is a P_{3} or H contains an isolated vertex and s(H) = 1, in which case χ^{∗}(G) = n + 1.

Proof. We first partition V (H) into m subsets V_{1}, …, V_{m} so that two vertices in H have the same closed neighborhood in H if and only if they are in the same subset. For any vertex x in H, we use f(x) to denote the vertex in K_{n} adjacent to x. For 1 ≤ i ≤ m, let U_{i} = f(V_{i}) denote the set of vertices in K_{n} adjacent to vertices in V_{i}.

We first prove the lower bound. Let c denote a good coloring of G using χ^{∗}(G) colors. Then we have the following observations.

(i) No two vertices in H can receive the same color. (ii) No two vertices in U_{i} can receive the same color for any fixed i, 1 ≤ i ≤ m. (iii) |c(V (K_{n})) ∩ c(V (H))| ≤ 1. Therefore we have χ^{∗}(G) ≥ |c(V (H))|+|c(V_{1})|−1 = n+s(H)−1, where |V_{1}| = max{|V_{i}| : 1 ≤ i ≤ m} = s(H).

If each component of H is a P_{3}, then we can easily check that χ^{∗}(G) ≥ n + 1. If s(H) = 1 and H contains an isolated vertex u, then clearly |c(V (K_{n}))| ≥ 2. Hence, χ^{∗}(G) ≥ n + 2 − 1 = n + 1.

We now prove the upper bound. Let v be a vertex in H that does not distinguish any edge of H. Without loss of generality, we may assume u_{1} is the vertex in U_{1} = f(V_{1}) adjacent to v. We also choose an arbitrary vertex u_{i} ∈ U_{i} for 2 ≤ i ≤ m. Let S_{1} = {1, 2, …, n} and S_{2} be a set of s(H) − 1 colors other than those in S_{1}. We now define a good coloring of G as follows.

(i) Color vertices in H with those colors in S_{1}, so that c(v) = 1 and no two vertices in H receive the same color;

(ii) c(u_{i}) = 1 for 1 ≤ i ≤ m; (iii) c(U_{i}−{u_{i}}) ⊆ S_{2} and no two vertices in U_{i}−{u_{i}} receive the same color for 1 ≤ i ≤ m; with the exception that c(u) = n + 1 for all u ∈ V (K_{n}) − {v_{1}} if each component of H is a P_{3} or H contains an isolated vertex and s(H) = 1. Then we can easily verify that c is a good coloring of G. ■

4. Bounds.

We first give a sharp lower bound for χ^{∗}(G) in terms of χ(G). This is a special case of a more general result whose proof can be found in Zhang [5].

Theorem 9. 1 + ⌈log_{2} χ(G)⌉ ≤ χ^{∗}(G). Furthermore, for all n ≥ 1 there exists a graph G such that χ(G) = n and χ^{∗}(G) = 1 + ⌈log_{2} n⌉.

For a positive integer k and a graph G, a coloring c of the vertices of G is a good distance-k-coloring of G if and only if c(u) ≠ c(v) for distinct vertices u, v with d_{G}(u, v) ≤ k. If we assign each vertex G a different color we have a good distance-k-coloring of G for all positive integers k. Let χ_{k}(G) denote the mininum number of colors required in a good distance-k-coloring of G. Hence, χ_{k}(G) ≤ n when G has order n. We require the following result.

Lemma 10. For a graph G with Δ = Δ(G) ≥ 3,

χ_{k}(G) ≤ \frac{Δ(Δ − 1)^{k} − 2}{Δ − 2}.

Proof. Let ℓ denote the integer \frac{Δ(Δ−1)^{k}−2}{Δ−2}. We apply the Greedy Algorithm to any ordering v_{1}, …, v_{n} of the vertices of G. First color v_{1} with color 1. Assume we have a good distance-k-coloring of v_{1}, …, v_{j} using the colors 1, …, ℓ. Now

#{v_{i} : d_{G}(v_{i}, v_{j+1}) ≤ k, 1 ≤ i ≤ j} ≤ Δ + Δ(Δ − 1) + ⋯ + Δ(Δ − 1)^{k−1}

= \frac{Δ(Δ − 1)^{k} − Δ}{Δ − 2} = ℓ − 1.

Hence, at most ℓ − 1 colors are present among these vertices and we color v_{j+1} with the smallest color which has not been used. ■

Remark. Our proof also shows that χ_{k}(G) ≤ 2k + 1 when Δ(G) = 2.

Theorem 11. For a graph G,

χ^{∗}(G) ≤ χ_{3}(G)

hence, for Δ = Δ(G) ≥ 3,

χ^{∗}(G) ≤ \frac{Δ(Δ − 1)^{3} − 2}{Δ − 2}.

Proof. Let c be a good distance-3-coloring of G using χ_{3}(G) colors. Hence, c is a proper coloring of G. For edge uv of G with w ∈ N_{G}[u]−N_{G}[v], c(w) ∉ c(N_{G}[v]) since d_{G}(w, x) ≤ 3 for all x ∈ N_{G}[u] and, hence, c(N_{G}[u]) ≠ c(N_{G}[v]) (w ∈ N_{G}[v] − N_{G}[u] is similar). Consequently, c is a good coloring of G. ■

Remark. The bound given in Theorem 11 may be quite weak; we know of no graphs where equality is attained.

5. Bounds for Regular Graphs with Girth at Least Four.

We use the following inequality,

1 − x ≤ e^{−x}  for x ∈ ℝ.  (4)

For integers k, n with 1 ≤ k ≤ n, let (n)_{k} = n(n − 1) ⋯ (n − k + 1). Then (4) implies

(n)_{k} ≤ n^{k}e^{−\binom{k}{2}/n} ≤ e^{1/2}n^{k}e^{−k^{2}/2n}, n^{k}.  (5)

For nonnegative integers k, ℓ, n with k ≤ k + ℓ ≤ n − 1, we use

\binom{n − ℓ}{k}\binom{n}{k}^{−1} ≤ e^{−kℓ/n}  (6)

We also use the following results for the Stirling number S(n, k) of the second kind (see [2; p. 204–208]),

S(n, 2) = 2^{n−1} − 1 for n ≥ 1.  (7)

and

S(n, k) ≤ \binom{n − 1}{k − 1}k^{n−k} for 1 ≤ k ≤ n.  (8)

We make use of the Lovász Local Lemma (see [3]).

Lemma. (Erdös and Lovász) Let A_{1}, A_{2}, …, A_{n} be events in an arbitary probability space. Suppose that each event A_{i} is mutually independent of all, but at most d, of the other events A_{j} and that P (A_{i}) ≤ p for all 1 ≤ i ≤ n. If

ep(d + 1) ≤ 1

then

P (⋀_{i=1}^{n} \overline{A}_{i}) > 0.

(As usual \overline{A} denotes the complement of the event A.)

We are able to substantially improve the bound in Theorem 11 for regular graphs with girth at least four using random colorings of the vertices. Observe that if a graph G has girth(G) ≥ 4 and uv ∈ E(G), then N_{G}[u] ≠ N_{G}[v] when d_{G}(u) + d_{G}(v) ≥ 3.

Theorem 12. For an r-regular graph G of order n with r ≥ 61 and girth(G) ≥ 4,

χ^{∗}(G) ≤ ⌈er⌉.

Proof. We initially assume only that r ≥ 3. Independently, color the vertices of G randomly from [k] = {1, …, k} according to a uniform distribution. Hence, each coloring of G has probability k^{−n}. For uv ∈ E(G), let A_{uv} denote the event “c(N_{G}[u]) = c(N_{G}[v])”. Hence,

P (A_{uv}) = k^{−2r+1} + \binom{k}{2}S(r + 1, 2)2![2S(r − 1, 2), 2!

+ 3S(r − 1, 1)1!]k^{−2r} + ∑_{j=3}^{r+1} \binom{k}{j}S(r + 1, j)j![2S(r − 1, j)j!

+ 3S(r − 1, j − 1)(j − 1)! + S(r − 1, j − 2)(j − 2)!]k^{−2r}.

Here \binom{k}{j} is the number of ways to select j colors; S(r + 1, j) is the number of ways to partition N_{G}[u] into j nonempty sets; j! is the number of ways to assign the j colors to these sets; 2S(r − 1, j)j! arises when the color(s) at u, v appear again in N_{G}(v) − {u}; 3S(r − 1, j − 1)(j − 1)! arises when u, v have the same color which does not appear again in N_{G}(v) − {u} or when u, v have different colors exactly one of which appears again in N_{G}(v) − {u}; and S(r − 1, j − 2)(j − 2)! arises when u, v have different colors neither of which appears in N_{G}(v) − {u}. (The cases j = 1, 2 are indicated separately.)

For 3 ≤ j ≤ r − 1, 0 ≤ i ≤ 2, (8), as well as, analysis of the cases i = 0, j = r, r + 1; i = 1, j = r + 1 implies

S(r − 1, j − i)(j − i)! ≤ \binom{r − 2}{j − i − 1}(j − i)!j^{r+1−j}

while (5), as well as, analysis of the above cases implies

\binom{r − 2}{j − i − 1}(j − i)! ≤ jr^{j−1}

so that

S(r − 1, j − i)(j − i)! ≤ r^{j−1}j^{r+2−j}.

Similarly, for k ≥ 1, (5) and (8) imply

\binom{k}{j}S(r + 1, j)j! ≤ e^{2}(ek)^{j}r^{j−1}j^{r+2−2j}e^{−j^{2}/2r}.

Hence,

P_{1} := ∑_{j=3}^{r+1} \binom{k}{j}S(r + 1, j)j![2S(r − 1, j)j!
+ 3S(r − 1, j − 1)(j − 1)! + S(r − 1, j − 2)(j − 2)!]k^{−2r}
≤\frac{6e^{2}}{r^{2}} ∑_{j=3}^{r} (\frac{ekr^{2}}{j^{3}} )^{j} j^{2r+4}e^{−j^{2}/2r}k^{−2r} + 8kr (\frac{r}{k} )^{r} .

For f(j) = (\frac{ekr^{2}}{j^{3}} )^{j} j^{2r+4}e^{−j^{2}/2r} we have f′(j) = f(j) [log (\frac{kr^{2}}{e^{2}j^{3}} ) + \frac{2r+4}{j} − \frac{j}{r} ] > f(j) log (\frac{kr^{2}}{ej^{3}} ) > 0 on [3, r] provided k ≥ er. Then

P_{1} ≤ 6e^{2}r^{3} (\frac{e^{1/2}r}{k} )^{r} + 8kr (\frac{r}{k} )^{r} ≤ 7e^{2}r^{3} (\frac{e^{1/2}r}{k} )^{r}  (9)

provided er ≤ k ≤ e^{7/2}r^{2}/8. Also (7) and (8) imply,

\binom{k}{2}S(r + 1, 2)2![2S(r − 1, 2)2! + 3S(r − 1, 1)1!]k^{−2r} ≤ k^{2} (\frac{4}{k^{2}} )^{r} .

Hence,

P (A_{uv}) ≤ k^{−2r+1} + k^{2} (\frac{4}{k^{2}} )^{r} + 7e^{2}r^{3} (\frac{e^{1/2}r}{k} )^{r} ≤ 8e^{2}r^{3} (\frac{e^{1/2}r}{k} )^{r}

when er ≤ k ≤ e^{7/2}r^{2}/8. The event A_{uv} depends only on the events A_{wx} with d_{G}(uv, wx) ≤ 2; hence, at most 2r^{3} − 1 such events A_{wx}. For k = ⌈er⌉ with r ≥ 61

16e^{3}r^{6} (\frac{e^{1/2}r}{k} )^{r} ≤ 16r^{6}e^{−(r−6)/2} < 1

and the Lovász Local Lemma implies

P ( ⋀_{uv∈E} \overline{A}_{uv}) > 0.

Consequently, there exists a good k-coloring of G and χ^{∗}(G) ≤ ⌈er⌉. ■

The proof of Theorem 12, using (9) with er ≤ k ≤ e^{7/2}r^{2}/8, immediately gives the following result.

Corollary 13. For an r-regular graph G with 7 ≤ r ≤ 60 and girth(G) ≥ 4,

χ^{∗}(G) ≤ ⌈c_{r}r⌉

where

c_{r} = e^{1/2}(16e^{3}r^{6})^{1/r}.

Remark. Observe that c_{r} is a decreasing function of r on [2, ∞) with c_{7} ≐ 19.937, c_{60} ≐ 2.7337 > e > 2.6496 ≐ c_{61}.

We can extend Corollary 13 to 3 ≤ r ≤ 60 by analyzing the proof of Theorem 12. However, for small values of r, the required probabilities can be found exactly rather than estimated. We give only the result for cubic graphs.

Theorem 14. For a cubic graph G with girth(G) ≥ 4,

χ^{∗}(G) ≤ 15.

Proof. We use the probability space and notation of Theorem 12 and give only a brief outline of the proof. For uv ∈ E(G), let the neighbors of u be u_{1}, u_{2}, v and the neighbors of v be u, v_{1}, v_{2}. Necessarily, u, v, u_{1}, u_{2}, v_{1}, v_{2} are distinct. Let p denote the number of colors present among u, v, u_{1}, u_{2}, v_{1}, v_{2} and (c_{1}, …, c_{p}) denote the event “among the colors of u, v, u_{1}, u_{2}, v_{1}, v_{2}, some color occurs c_{1} times, another color occurs c_{2} times, etc”. Finally, observe that the event “the colors of u_{1}, u_{2}, v_{1}, v_{2} occur exactly once among the colors of u, v, u_{1}, u_{2}, v_{1}, v_{2}” is a subevent of \overline{A}_{uv} so that p ≥ 5 is a subevent of \overline{A}_{uv}. By direct enumeration and independence,

P (A_{uv} and (6)) = \frac{k}{k^{6}} , P (A_{uv} and (1, 5)) = \frac{2k(k − 1)}{k^{6}}, P (A_{uv} and (2, 4)) = \frac{13k(k − 1)}{k^{6}},

P (A_{uv} and (3, 3)) = \frac{10k(k − 1)}{k^{6}}, P (A_{uv} and (1, 1, 4)) = \frac{k(k − 1)(k − 2)}{k^{6}},

P (A_{uv} and (1, 2, 3)) = \frac{16k(k − 1)(k − 2)}{k^{6}}, P (A_{uv} and (2, 2, 2)) = \frac{10k(k − 1)(k − 2)}{k^{6}},

P (A_{uv} and (1, 1, 1, 3)) = 0, and P (A_{uv} and (1, 1, 2, 2)) = \frac{2k(k − 1)(k − 2)(k − 3)}{k^{6}}.

Hence,

P (A_{uv}) = \frac{2k^{3} + 15k^{2} − 34k + 18}{k^{5}}.

Now A_{uv} depends on at most 28 other events and for k ≥ 15,

29e \frac{2k^{3} + 15k^{2} − 34k + 18}{k^{5}} < 1

so that the Lovász Local Lemma implies

P ( ⋀_{uv∈E} \overline{A}_{uv}) > 0.

Consequently, there exists a good 15-coloring of G and χ^{∗}(G) ≤ 15. ■

Suppose G has no isolated edges and girth(G) ≥ 4. We say uv ∈ E(G) is attached to w ∈ V (G) − {u, v} provided uw or vw ∈ E(G). Since girth(G) ≥ 4, precisely one of uw or vw is in E(G). A set W ⊆ V (G) is an attachment set of G provided each edge in G is attached to some vertex in W. Clearly, V (G) is an attachment set of G. Let τ(G) denote the smallest cardinality of an attachment set of G. Hence, τ(G) ≤ n when G has order n. In fact, τ(G) ≤ n − 1 according to Lemma 7. We require the following result.

Lemma 15. If G has no isolated edges and girth(G) ≥ 4, then

χ^{∗}(G) ≤ 1 + τ(G).

Proof. Let W be an attachment set of G with |W | = τ(G) = τ. Color each vertex of W with a distinct color from \{1, …, τ\} and color each vertex of \overline{W} with color τ + 1. Clearly, this coloring is a good coloring of G. ■

Our final result improves the bound in Theorem 12 for dense regular graphs with girth at least 4.

Theorem 16. For an r-regular graph G of order n ≥ 48 with r ≥ 3 and girth(G) ≥ 4,

χ^{∗}(G) ≤ 1 + ⌈\frac{n}{2r} log 2er^{3}⌉ .

Proof. Randomly choose W ⊆ V (G) with |W | = k according to a uniform distribution. Hence, P (W) = \binom{n}{k}^{−1}. For uv ∈ E(G), let A_{uv} denote the event “uv is not attached to any vertex in W ”. Hence,

P (A_{uv}) = P (W ∩ (N_{G}(u) ∪ N_{G}(v)) = ∅) = \binom{n − 2r}{k}\binom{n}{k}^{−1}.

For n ≥ 48, r ≥ 3 and k = ⌈\frac{n}{2r} log 2er^{3}⌉, (6) implies

P (A_{uv}) ≤ e^{−2rk/n} ≤ (2er^{3})^{−1}.

As in Theorem 12, A_{uv} depends on at most 2r^{3} − 1 other events A_{wx}, and the Lovász Local Lemma implies

P ( ⋀_{uv∈E(G)}\overline{A}_{uv}) > 0.

Consequently, there exists an attachment set of G having cardinality k and our result now follows from Lemma 15. ■

6. Open Problems.

In this section we give three open problems.

(1) Find a good upper bound for χ^{∗}(G) in terms of χ(G). As a consequence of Theorem 8, χ^{∗}(2K_{n} + 1 − factor) = 2χ(G) − 1, which is the largest such value we have been able to find.

(2) Find a good upper bound for χ^{∗}(G) in terms of Δ(G). In Theorem 11, a cubic upper bound was given for χ^{∗}(G) in terms of Δ(G). Perhaps, there is a linear upper bound for χ^{∗}(G) in terms of Δ(G).

(3) Determine the quality of the upper bound for χ^{∗}(G) given in Theorems 12 and 16.

References

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, North-Holland, New York, 1980.

[2] L. Comtet, Advanced Combinatorics, D. Reidel, Boston, 1974.

[3] P. Erdös and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets (A. Hajnal et al., eds.), North-Holland (1975), 609–628.

[4] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.

[5] G. Zhang, Open neighborhood colorings of graphs, in preparation.