GRAPHS WITH SMALL GENERALIZED CHROMATIC NUMBER

W. F. Smyth

Department of Computer Science & Systems McMaster University Hamilton, Ontario L8S 4K1 Canada

School of Computing Curtin University of Technology Perth WA 6001 Australia

ABSTRACT

Let G = (V, E) denote a finite simple undirected connected graph of order n = |V | and diameter D. For any integer k ∈ [1, D], a proper k-colouring of G is a labelling of the vertices V such that no two distinct vertices at distance k or less have the same label. We let γ_{k}(G), the k-chromatic number of G, denote the least number of labels required to achieve a proper k-colouring of G. In this paper we show that there exists an infinite class G^{∗} of graphs of order n and diameter D ≥ 3 such that, over all graphs G ∈ G^{∗}, γ_{D−1}(G) ∈ Θ(\sqrt{Dn}). Constructions are specified for graphs in the class G^{∗}.

1 INTRODUCTION

Let G = (V, E) denote a finite simple undirected connected graph of order n = |V | and diameter D > 0. For any integer k ∈ [1, D], a proper k-colouring of G is a labelling of the vertices V such that no two distinct vertices at distance k or less have the same label. For given G, we let γ_{k}(G), the k-chromatic number of G, denote the least number of labels required to achieve a proper k-colouring of G.

Problems associated with the estimation of the k-chromatic number were surveyed some years ago by Gionfriddo [G87]. A common approach has been to define the k-density ρ_{k}(G) to be the maximum order over all subgraphs of G with diameter k. (For example, if k = 1 and G is triangle-free, then ρ_{1}(G) = 2.) The nonnegative quantity

γ′_{k}(G) = γ_{k}(G) − ρ_{k}(G)

is then considered; in particular, attention focusses on small values of k and small values of γ′_{k}(G) — that is, cases in which the k-density is close to the k-chromatic number. Now let v_{k}(h) denote the least integer such that there exists a graph G of order v_{k}(h) for which γ′_{k}(G) = h. (For example, if k = 1 and h = 0, then v_{1}(0) = 2 corresponding to G = P_{2}, the path of length 1.) Some progress has been made establishing bounds on v_{k}(h) in more general cases [GV85], but exact calculation seems to be very difficult, even for k = 2 and small values of h.

In this paper, a different approach is adopted: bounds for γ_{k}(G) are related to the diameter of G. It turns out that, for k = D − 1, it is possible to determine quite sharp bounds which correspond to interesting constructions.

Typeset by AMS-TEX

Thus, for each choice D = 1, 2, …. and for every integer n > D, let G_{D,n} denote the class of all graphs G of diameter D and order n. Then, over all graphs G ∈ G_{D,n}, let α_{D,n,k} (respectively, β_{D,n,k}) denote the minimum (respectively, maximum) value attained by γ_{k}(G). As Theorem 1.1 shows, the upper bound is easy to determine:

Theorem 1.1 β_{D,n,k} = n − D + k. Proof We look for the greatest number of labels that can possibly be used in a

minimum proper k-colouring of G. Observe first that there exists a shortest path P_{D+1} in G of length D. Then a minimum proper k-colouring of P_{D+1} requires k + 1 distinct labels. If the remaining n − D − 1 vertices of G must all be given labels distinct from the k + 1 labels used in P_{D+1}, then a total of n−D+k labels will be used to colour G. Thus this total is the maximum possible value that γ_{k}(G) could take. But this value is actually attained for the graph G formed by joining one end vertex of a path P_{D} of length D − 1 to every vertex of a complete graph K_{n−D}: the resulting graph G then has n vertices, diameter D, and k-chromatic number n − D + k. □

As a special case of this result, we see that β_{D,n,D} = n; since also α_{D,n,D} = n, it follows that

γ_{D}(G) = n

for any given graph G. At the other extreme, for k = 1, Theorem 1.1 tells us that β_{D,n,1} = n − D + 1. To determine α_{D,n,1}, consider the graph G formed by joining n−D isolated vertices \overline{K}_{n−D} to one end of a path P_{D} of length D−1. The resulting graph G has n vertices, diameter D, and 1-chromatic number 2. (Indeed, G may be any tree on n vertices with diameter D.) Since for any k ≥ 1, α_{D,n,k} > 1, it follows that α_{D,n,1} = 2, so that, for any given graph G,

2 ≤ γ_{1}(G) ≤ n − D + 1.

For 1 < k < D, the value of α_{D,n,k} is more difficult to determine. In the remainder of this article, we consider the case k = D − 1; to simplify notation, we write α_{D−1} ≡ α_{D,n,D−1}.

For the estimation of α_{D−1}, the first interesting case that arises is D = 3, which we now begin to consider. It follows from Theorem 5 of [BRZ68] that if D ≥ 3 for a graph G, then the diameter of the complement graph \overline{G} is \overline{D} ≤ 3. (This result was later rediscovered in [HR85].) Recall now the result of Bloom, Kennedy and Quintas [BKQ87] that G has diameter 2 if and only if \overline{G} is not empty and \overline{G} is not spanned by a double star. (A spanning double star of G is a spanning tree of G which consists of two stars with centres u and v joined by the edge uv.) Thus for D = 3 there are exactly two possibilities:

(1) \overline{D} = 3, in which case G is spanned by a double star;

(2) \overline{D} = 2, in which case G is NOT spanned by a double star.

In this section we deal with the first and more straightforward of these possibilities:

Theorem 1.2 Let G′_{3,n} denote the set of all graphs G ∈ G_{3,n} with complements \overline{G} ∈ G_{3,n}. Denote by α′_{2} the restriction of α_{2} to G′_{3,n}. Then

α′_{2} = ⌈n/2⌉ + 1.

Proof Since G is spanned by a double star, we may divide the vertices V into three non-empty sets U, S and T: U consists of the centres of the two spanning stars, S consists of the radial vertices of one star, T the radial vertices of the other. Without loss of generality, suppose that |S| ≤ |T |. Now consider a proper 2-colouring of G. We see that all labels in S ∪ U must be distinct, as so also must all labels in T ∪U. Then, for given n, a minimum number of labels will be used if and only if the following two conditions are satisfied:

(1) every label used in S is also used in T;

(2) |T | − |S| ≤ 1.

When n is even, so that |T | = |S|, we have n = 2|S| + 2 and γ_{2}(G) = n/2 + 1. For odd n, we have similarly |T | = |S| + 1, n = 2|S| + 3, and γ_{2}(G) = (n + 1)/2 + 1. Thus a double star which satisfies condition (2) can be labelled to yield a minimum 2-colouring using ⌈n/2⌉ + 1 labels. From this fact the result follows. □

As we shall see below, the lower bound of Theorem 1.2 is exceptional. It appears that for other classes of graphs, α_{D−1} ∈ O(\sqrt{Dn}). We begin our consideration of these graphs in Section 2, by investigating the graphs of diameter 3 whose complements have diameter 2. In Section 3 we look in detail at constructions for graphs of even diameter D ≥ 4, and then in Section 4 we indicate how these constructions may be extended to graphs of odd diameter D ≥ 5.

2 DIAMETER D = 3

In this section we study graphs G ∈ G′′_{3,n}, where G′′_{3,n} denotes the set of all graphs of G_{3,n} whose complements are in G_{2,n}. In particular, we display an infinite subclass G∗_{3,n} ⊂ G′′_{3,n} of graphs G whose 2-chromatic number

γ_{2}(G) = \sqrt{2n + 4} − 1.

The graphs in this subclass are constructed based on an integer parameter ν = 3, 4, …., and so we denote them G_{ν}. We shall see that G_{ν} has order n = 2(ν^{2} − 1), size m = ν(ν^{2} − 1), and of course diameter D = 3.

To construct the G_{ν}, we begin with two copies of the complete graph K_{ν−1}, which we call K_{ν−1}^{(1)} and K_{ν−1}^{(2)}. Corresponding to each i = 1, 2, we introduce ν − 1

disjoint sets of ν isolated vertices \overline{K}_{ν}, which we call \overline{K}_{ν}^{(i,1)}, \overline{K}_{ν}^{(i,2)}, …, \overline{K}_{ν}^{(i,ν−1)}. Let U^{(i)} = {u_{1}^{(i)}, u_{2}^{(i)}, …, u_{ν−1}^{(i)}} denote the vertices of K_{ν−1}^{(i)}, and for each j =

1, 2, …, ν −1, let V^{(i,j)} = \{v_{1}^{(i,j)}, v_{2}^{(i,j)}, …, v_{ν}^{(i,j)}\} denote the vertices of \overline{K}_{ν}^{(i,j)}. We now introduce two sets of edges (beyond those already found in the K_{ν−1}^{(i)}):

(1) For every i = 1, 2; j = 1, 2, …, ν − 1; h = 1, 2, …, ν: u_{j}^{(i)}v_{h}^{(i,j)} is an edge. (This joins each vertex of K_{ν−1}^{(i)} to each of ν vertices in one of the sets V^{(i,j)}.)

(2) For every j = 1, 2, …, ν − 1; j′ = 1, 2, …, ν − 1; h = 1, 2, …, ν: v_{h}^{(1,j)}v_{h′}^{(2,j′)} is an edge if and only if h′ is computed by the following algorithm:

h′ ⟵ j + j′ + h − 1;
if h′ > ν then
{h′ ⟵ h′ − ν;
if j + j′ − 1 = ν then
h′ ⟵ h′ + 1}.

(This joins each vertex of V^{(1,j)} to a single vertex in each of V^{(2,j′)}, j′ = 1, 2, …, ν − 1, in such a way that v_{h}^{(1,j)}v_{h}^{(2,j′)} is never an edge for any choice of j, j′ and h.)

To the vertices of G_{ν} we now assign labels L as follows: for every i = 1, 2 and for every j = 1, 2, …, ν − 1 set

L(u_{j}^{(i)}) ⟵ j; and
∀h = 1, 2, …, ν : L(v_{h}^{(i,j)}) ⟵ ν + h − 1.

Thus a total of 2ν − 1 distinct labels are assigned; we claim that γ_{2}(G_{ν}) = 2ν − 1.

To prove this claim, we first show that in fact G_{ν} has diameter D = 3. Consider first the edges v_{h}^{(1,j)}v_{h′}^{(2,j′)} and observe that, for fixed j and j′, as h assumes the values 1, 2, …, ν, h′ assumes distinct values in the cyclic permutation of 1, 2, …, ν which begins at one of {j + j′, j + j′ − ν, j + j′ − ν + 1}; thus every vertex of K_{ν}^{(1,j)} is adjacent to a single distinct vertex of K_{ν}^{(2,j′)}. Clearly this statement is true also when the superscripts 1 and 2 are interchanged. It follows then that every vertex of K_{ν−1}^{(i)} is distance exactly 2 from every vertex of \overline{K}_{ν}^{(3−i,j)} for every j = 1, 2, …, ν−1, and hence distance exactly 3 from every vertex of K_{ν−1}^{(3−i)}. Furthermore, we see that whenever v_{h}^{(i,j)}v_{h′}^{(3−i,j′)} is an edge, then v_{h}^{(i,j)} is distance exactly 3 from every vertex v_{h′′}^{(3−i,j′)}, where h′′ ∈ [1, ν] and h′′ ≠ h′. Finally, observe that v_{h}^{(i,j)} is distance exactly 2 from every vertex v_{h′}^{(i,j)}, h′ ≠ h, and distance exactly 3 from every vertex v_{h′}^{(i,j′)}, j′ ≠ j. We conclude that D = 3 and note that, moreover, every vertex of G_{ν} is peripheral. Note also that G_{ν} is not spanned by a double star.

To show that the labelling specified yields a proper 2-colouring, it is necessary to show that all vertices with the same label are distance 3 from each other. This is clearly true for the vertices of K_{ν−1}^{(i)}. To prove this result for the labels ν, ν + 1, …, 2ν − 1, it suffices to show that

* v_{h}^{(i,j)}v_{h}^{(3−i,j′)} is never an edge;

* v_{h}^{(i,j)} is always adjacent to ν − 1 vertices with distinct labels. The first of these propositions is a direct consequence of the method of calculation of h′ specified in (2) above: if h′ = h then either j + j′ − 1 = 0, an impossibility, or j+j′−1 = ν, in which case the value of h′ is incremented by one, so as to be no longer equal to h. To prove the second proposition, consider first the edges joining a vertex v_{h}^{(1,j)} to V^{(2,1)}, for every h = 1, 2, …, ν. These edges will be v_{h}^{(1,j)}v_{h_{1}}^{(2,1)}, where h_{1} is one element of the set H_{0} = {j + h, j + h − ν, j + h − ν + 1}. More generally, the vertices v_{h_{1}}^{(2,1)}, v_{h_{2}}^{(2,2)}, …, v_{h_{ν−1}}^{(2,ν−1)} of V^{(2,1)}, V^{(2,2)}, …, V^{(2,ν−1)}, respectively, which are adjacent to v_{h}^{(1,j)} are identified by the cyclic permutation (h_{1}, h_{2}, …, h_{ν−1}) of 1, 2, …, ν which begins at the element of H_{0} specified by (2) and omits h. These vertices will have ν − 1 distinct labels ν + h_{1} − 1, ν + h_{2} − 1, …, ν + h_{ν−1} − 1. A similar argument establishes also that vertices v_{h_{1}}^{(1,1)}, v_{h_{2}}^{(1,2)}, …, v_{h_{ν−1}}^{(1,ν−1)} adjacent to

a given vertex v_{h}^{(2,j)} all have distinct labels. We conclude that γ_{2}(G_{ν}) = 2ν − 1, as required. We state this result formally as follows:

Theorem 2.1 For every integer ν ≥ 3, the graphs G_{ν} of order n = 2(ν^{2} − 1) and diameter 3 have 2-chromatic number \sqrt{2n + 4} − 1. Thus

α_{2} ∈ O(\sqrt{n}). □

Finally, we remark that for ν = 3 a slight improvement can be made to the above construction, yielding n = 2ν^{2} = 18 and γ_{2}(G_{3}) = \sqrt{2n} − 1 = 5.

3 EVEN DIAMETER D ≥ 4

In this section we first present a construction for graphs G ∈ G_{4,n} for which the (D-1)-chromatic number

γ_{D−1}(G) = ⌈2\sqrt{n − 1}⌉.

We then show how to generalize this construction to graphs G ∈ G_{2d,n} of arbitrary even diameter D = 2d, where d = 2, 3, ….

We note in passing the result of Bosák, Rosa and Znám [BRZ68] (later rediscovered in [S86]) that for graphs G of diameter D ≥ 4, the complement graph \overline{G} must have diameter \overline{D} = 2. Thus the special case dealt with in Theorem 1.2 does not arise for D ≥ 4.

Consider a graph G = (V, E) ∈ G_{4,n}. There exists a shortest path s_{1}u_{1}uu_{2}s_{2} in G joining peripheral vertices s_{1} and s_{2}. Let U = {u, u_{1}, u_{2}}, and for j = 1, 2 let S_{j} denote the set of all vertices v^{(j)} ≠ u such that u_{j}v^{(j)} ∈ E. Then, in particular, s_{j} ∈ S_{j}. Observe that a proper (D − 1)-colouring of G requires that all the labels assigned to U ∪ S_{j} be distinct; that is,

γ_{3}(G) ≥ max_{j=1,2} |S_{j}| + 3.

The lower bound can of course be attained by a graph G whose every shortest path from S_{1} to S_{2} is of length D.

Suppose now more generally that V contains p ≥ 2 distinct subsets S_{1}, S_{2}, …, S_{p} such that every shortest path from one subset to another

* is of length D;

* passes through u. Then the graph G of least order n satisfying these conditions has vertex set V = U ∪ (∪_{j=1}^{p}S_{j}), where U = {u, u_{1}, u_{2}, …, u_{p}} and

γ_{3}(G) = max_{1≤j≤p} |S_{j}| + (p + 1).

Let s^{∗} denote the average order of the S_{j}; that is, s^{∗} = (|S_{1}| + |S_{2}| + ⋯ + |S_{p}|)/p. Then

n = ps^{∗} + p + 1.  … (3.1)

Observe now that γ_{3} can be minimized by imposing the further condition on G that

⌊s^{∗}⌋ ≤ |S_{j}| ≤ ⌊s^{∗}⌋ + 1,  … (3.2)

for every j = 1, 2, …, p. Then, using (3.1),

\begin{aligned}γ_{3}(G) & = ⌈s^{∗}⌉ + p + 1 \\ & = ⌈(n − 1)/p⌉ + p, \end{aligned}

an expression which achieves its minimum value for

p = ⌈\sqrt{n − 1}⌉.  … (3.3)

Thus, if the subsets of V are chosen to satisfy (3.2) and (3.3), then

γ_{3}(G) = ⌈(n − 1)/⌈\sqrt{n − 1}⌉⌉ + ⌈\sqrt{n − 1}⌉.  … (3.4)

We now state three noteworthy identities (left as exercises for the reader). For any positive real number x, let

C(x) ≡ ⌈x/⌈\sqrt{x}⌉⌉ + ⌈\sqrt{x}⌉.

For x ≥ 1, let

F (x) ≡ ⌈x/⌊\sqrt{x}⌋⌉ + ⌊\sqrt{x}⌋.

Then

C(x) = ⌈2\sqrt{⌈x⌉}⌉;  … (3.5a)
F (x) = ⌈2\sqrt{⌈x⌉}⌉,  … (3.5b)

if there exists no integer N such that N^{2} − 1 < x < N^{2}; and

F (x) = ⌈2\sqrt{⌈x⌉}⌉ + 1,  … (3.5c)

otherwise. Thus, in view of (3.5a), (3.4) becomes

γ_{3}(G) = ⌈2\sqrt{n − 1}⌉.  … (3.6)

A graph G which satisfies (3.6) may be characterized as a graph of diameter D = 4, radius d = 2, a single centre u, and n − ⌈\sqrt{n − 1}⌉ − 1 peripheral nodes divided as equally as possible into ⌈\sqrt{n − 1}⌉ mutually peripheral subsets. An example of such

a graph is formed by ⌈\sqrt{n − 1}⌉ complete graphs K_{s}, where ⌈s^{∗}⌉ + 1 ≤ s ≤ ⌈s^{∗}⌉ + 2, each with a single vertex adjacent to u.

Consider now a graph G ∈ G_{D,n}, where D = 2d for some integer d ≥ 2, and suppose as before that the vertex set V contains p ≥ 2 distinct subsets S_{1}, S_{2}, …, S_{p} as defined above. Defining s^{∗} as before, we find

n = ps^{∗} + p(d − 1) + 1,  … (3.7)

analogous to (3.1). Then, applying (3.2) and (3.7), we find that

\begin{aligned}γ_{D−1}(G) & = ⌈s^{∗}⌉ + p(d − 1) + 1 \\ & = ⌈(n − 1)/p⌉ + (d − 1)(p − 1) + 1. \end{aligned}  … (3.8)

Now consider the function γ^{∗}(p) = (n − 1)/p + (d − 1)(p − 1) + 1, differentiable in any interval not containing p = 0. This function attains its minimum for

\frac{dγ^{∗}}{dp} = −(n − 1)/p^{2} + (d − 1) = 0;

that is, for p = \sqrt{\frac{n−1}{d−1}}. Then (3.8) is minimized by choosing either p = p_{1} ≡

⌈\sqrt{\frac{n−1}{d−1}}⌉ or p = p_{2} ≡ ⌊\sqrt{\frac{n−1}{d−1}}⌋. To estimate the minimum value of (3.8), consider

first

γ^{∗}(p_{1}) = (d − 1)\{(\frac{n − 1}{d − 1})/⌈\sqrt{\frac{n − 1}{d − 1}}⌉ + ⌈\sqrt{\frac{n − 1}{d − 1}}⌉ − 1\} + 1.

We see that

(d − 1)(C(\frac{n − 1}{d − 1}) − 2) ≤ γ^{∗}(p_{1}) ≤ (d − 1)(C(\frac{n − 1}{d − 1}) − 1),

where C(\frac{n−1}{d−1}) is given by (3.5a). From (3.5b) and (3.5c), it follows then that

γ^{∗}(p_{1}) ≤ γ^{∗}(p_{2}) ≤ γ^{∗}(p_{1}) + 1;

and since, for every positive value of p,

0 ≤ γ_{D−1}(G) − γ^{∗}(p) ≤ 1,

we have the main result of this section:

Theorem 3.1 For every even integer D = 2d, d ≥ 2, and for every integer n > D, there exists a graph G ∈ G_{D,n} such that

(d − 1)(⌈2\sqrt{⌈\frac{n − 1}{d − 1}⌉}⌉ − 2) ≤ γ_{D−1}(G) − 1 ≤ (d − 1)(⌈2\sqrt{⌈\frac{n − 1}{d − 1}⌉}⌉ − 1).

Hence α_{D−1} ∈ O(\sqrt{Dn}). □

As in the special case d = 2, a graph G which satisfies Theorem 3.1 is characterized by radius d, a single centre u, and n − (d − 1)p_{1} − 1 peripheral nodes divided

as equally as possible into p_{1} mutually peripheral subsets, where p_{1} = ⌈\sqrt{\frac{n−1}{d−1}}⌉.

4 ODD DIAMETER D ≥ 5

Here we consider graphs G ∈ G_{2d+1,n} of odd diameter D = 2d + 1, d ≥ 2. The construction is similar to the construction for even diameter 2d; the main difference is that the centre u is replaced by a complete subgraph K_{p}, which thus increases the diameter by one. The results apply also to the case D = 3 (d = 1).

As before, we suppose that V contains p ≥ 2 mutually peripheral subsets S_{1}, S_{2}, …, S_{p} such that every shortest path from one subset to another passes through at least two vertices of the “central” complete subgraph K_{p}. If as before s^{∗} denotes the average size of |S_{j}|, j = 1, 2, …, p, then, analogous to (3.1),

n = p(s^{∗} + d).  … (4.1)

By choosing the orders of the S_{j} to be as nearly equal as possible, we can make

\begin{aligned}γ_{D−1}(G) & = s^{∗} + pd \\ & = n/p + (p − 1)d, \end{aligned}  … (4.2)

from (4.1). We find then that γ_{D−1}(G) is minimized for p = ⌊\sqrt{n/d}⌋ or ⌈\sqrt{n/d}⌉. Substituting these values into (4.2) and applying (3.5a)-(3.5c), we find

Theorem 4.1 For every odd integer D = 2d + 1, d ≥ 1, and for every integer n > D, there exists a graph G ∈ G_{D,n} such that

d(⌈2\sqrt{⌈n/d⌉}⌉ − 2) ≤ γ_{D−1}(G) ≤ d(⌈2\sqrt{⌈n/d⌉}⌉ − 1).

Hence α_{D−1} ∈ O(\sqrt{Dn}). □

Note that in the special case D = 3, the construction of Section 2 yields a lower (D − 1)-chromatic number than the construction given here. More generally, it is not known whether the constructions given in this paper are best possible, in the sense of yielding, for given D and n, the least possible value of γ_{D−1}.

REFERENCES

[BKQ87] Gary S. Bloom, John W. Kennedy & Louis V. Quintas, A characterization of graphs of diameter 2, Amer. Math. Monthly 94 (1987) 37-38.

[BRZ68] J. Bosák, A. Rosa & Š. Znám, On decompositions of complete graphs into factors with given diameters, Theory of Graphs (Proc. Colloq. Tihany 1966, eds. P. Erdős & Gy. Katona), Akadémia Kiadó (1968) 37-56.

[G87] Mario Gionfriddo, A short survey on some generalized colourings of graphs, Ars Combinatoria 24B (1987) 155-163.

[GV85] Mario Gionfriddo & Scott Vanstone, On L_{2}-colourings of a graph, J. Inf. Optim. Sci. 6 (1985) 243-246.

[HR85] Frank Harary & Robert W. Robinson, The diameter of a graph and its complement, Amer. Math. Monthly 92 (1985) 211-212.

[S86] Philip D. Straffin Jr., letter to the editor, Amer. Math. Monthly 93 (1986) 76.

ACKNOWLEDGEMENT

This research was supported in part by Grant No. A8180 of the Natural Sciences & Engineering Research Council of Canada. The author is indebted to Sin-Min Lee of San Jose State University for introducing him to the problem in the first place and for stimulating discussions.