Interference-Minimizing Colorings of Regular Graphs.
Communications problems that involve frequency interference, such as the channel assignment problem in the design of cellular telephone networks, can be cast as graph coloring problems in which the frequencies (colors) assigned to an edge's vertices interfere if they are too similar. The paper considers situations modeled by vertex-coloring d-regular graphs with n vertices using a color set 1, 2,..., n, where colors i and j are said to interfere if their circular distance $\min \{ | i-j | , n- | i-j | \}$ does not exceed a given threshold value $\alpha$. Given a d-regular graph G and threshold $\alpha$, an interference-minimizing coloring is a coloring of vertices that minimizes the number of edges that interfere. Let $I_\alpha (G)$ denote the minimum number of interfering edges in such a coloring of $G$. For most triples $(n, \alpha ,d),$ we determine the minimum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain it. In determining when this minimum value is 0, we prove that for $r \geq 3$ there exists a d-regular graph G on n vertices that is r-colorable whenever $d \leq (1- \frac{1}{r}) n-1$ and nd is even. We also study the maximum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain this maximum in many cases.
Introduction
This paper is motivated by telecommunication problems such as the design of planar regions
for cellular telephone networks and the assignment of allowable frequencies to the regions. In
our graph abstraction, vertices are regions, edges are pairs of contiguous regions, and colors
correspond to frequencies. We presume that every region has the same number d of neighbors,
which leads to considering degree-regular graphs. Interference occurs between two regions if
they are neighbors and their frequencies lie within an interference threshold. We adopt the
simplifying assumption that the number of colors available equals the number n of regions, and
let ff denote the threshold parameter so that colors i and j in f1; ng interfere precisely
when their circularly-measured scalar distance is less than or equal to ff. Precedents for the
use of circularly-measured distance in graph coloring include Vince (1988) and Guichard and
Krussel (1992).
Our formulation leads to several interesting graph-theoretic problems. One is to determine
for any given d-regular graph G and threshold ff the minimum number I ff (G) of interfering
edges over the possible colorings of G. Another is: given parameters n; ff, and d, determine
the minimum and maximum values of I ff (G) and find graphs G that attain these values. We
focus on the latter problem. More specifically, let G(n; d) denote the set of undirected d-regular
graphs on n vertices, which have no loops or multiple edges, but may be disconnected. We
wish to determine the (global) minimum interference level '(n; ff; d), which is the minimum of
I ff (G) over G(n; d). For comparison purposes, we also wish to determine the (global) minimax
interference level L(n; ff; d), which is the maximum of I ff (G) over G(n; d). This latter problem
measures how badly off you would be if an adversary gets to choose G 2 G(n; d), and you can
then color G to minimize interference.
Our graph-theoretic model is an approximation to the frequency assignment problem for
cellular networks studied in Benveniste et al. (1995). In that paper the network of cellular
nodes is viewed as vertices of a hexagonal lattice   in R 2 , and the graph G is specified by a
choice of sublattice   0 of  , with being the index of the sublattice   0 in  . More
precisely, the vertices of G are cosets of and we draw an edge between two cosets if the
cosets are "close" in the sense that they contain vectors v, v 0 respectively with
where jj \Delta jj is a given norm on R 2 and x is a cutoff value. Such graphs 1 G are d-regular for
1 The graph G represents a fundamental domain of . In the cellular terminology a fundamental domain for
called a "reuse group." More generally a "reuse group" is a collection of contiguous cells that exhausts
all frequencies, with no two cells in the group using the same frequency.
some value of d; the usual nearest-neighbors case gives et al. (1995).
The frequency spectrum is also divided into cosets (modulo n), and nodes in the same coset
(mod   0 ) are assigned a fixed coset of frequencies (mod n). In cellular problems the graph G
is fixed (depending on   0 ). Typical parameters under consideration are
and n=ff about 2 or 3. From this standpoint the quantities '(n; ff; d) and L(n; ff; d) represent
lower and upper bounds for attainable levels of interference.
Related coloring problems motivated by the channel assignment problem are studied in Hale
(1980), Cozzens and Roberts (1982), Bonias (1991), Liu (1991), Tesman (1993), Griggs and
Liu (1994), Raychaudhuri (1994), Troxell (1996) and Guichard (1996) among others. Roberts
(1991) surveys the earlier part of this work. Factors that distinguish prior work from the
present investigation include our focus on regular graphs and the inevitability of interference
when certain relationships hold among n; ff and d.
Our main results give near-optimal bounds for '(n; ff; d) and L(n; ff; d) and identify d-regular
graphs and colorings that attain extremal values. Many interference-minimizing designs
use only a fraction of the available colors or frequencies. The most common number of colors
used in these optimal designs is
which is the maximum number of mutually noninterfering colors from f1; ng at threshold
ff. Detailed statements of theorems for '(n; ff; d) and L(n; ff; d) appear in Section 2. Proofs
follow in Sections 3 to 7.
In the course of our analysis we derive a graph-theoretic result of interest in its own right,
which is a condition for the existence of a d-regular graph having chromatic number - r.
Theorem 1.1. If r - 3, then G(n; d) contains an r-colorable graph if nd is even and
r
This result is proved in Section 5, and the proof can be read independently of the rest of the
paper. Note that if nd is odd then G(n; d) is the empty set.
We preface the results in the next section with a few comments to indicate where we are
headed. The case corresponds to no interference because the number of available colors
equals the number of vertices, and therefore '(n; 0; d) = L(n; 0; d) = 0. We assume that ff - 1
in the rest of the paper.
For degrees near 0 or n, namely 1, the set G(n; d) contains only one
unlabelled graph, so these cases are essentially trivial. We note at the end of Section 4 that
Our first main result in the next section, Theorem 2.1, applies to degree 2 and shows that
most values of ' and L for exception is that L(n; 2; 2) is approximately
n=3.
Subsequent results focus on d - 3, where we use the maximum number of noninterfering
colors fl to express the results. The case because then all colors interfere with
each other, so that #(edges of d) for most values of
(n; ff; d) is approximately
nd
Moreover, L(n; ff; d) = 0 whenever fl ? d, whereas if n is much larger than d, and d is
somewhat larger than fl, then L(n; ff; d) is approximately nd=(2fl).
Extremal graphs which attain '(n; ff; d) when ' ? 0 are usually connected, and the associated
coloring can often be achieved using fl noninterfering colors. On the other hand, graphs
that attain L(n; ff; d) when L ? 0 are usually disconnected and contain many copies of the
complete graph K d+1 . There are exceptions, however.
Our results imply that there is often a sizable gap between the values of ' and L. The
smallest instance of l ! L occurs at (n; ff; d) 2. Figure 1.1
shows the two graphs in G(6; 2) with interference-minimizing colorings for 2.

Figure

1.1 about here
A qualitative comparison of the regions where ' and L equal 0 and are positive is given in

Figure

1.2, where the coordinates are d=n and fl=n.

Figure

1.2 about here
2. Main Results
An undirected graph is simple if it has no loops or multiple edges. Let G(n; d) denote the
set of d-regular graphs on n vertices which are simple but which are not necessarily connected.
ng be a set of n colors with circular distance measure
and let ff 2 f0; be the threshold-of-interference parameter. A coloring of the vertex
set V (G) of graph d) is a [n]. The interference
I ff (G; f) of coloring f of G at threshold ff is
I ff (G; f) := jffx; yg
The minimum interference in G at threshold ff is
I ff (G) := min
f :V (G)![n]
I ff (G; f) :
We study the (global) minimum interference level
'(n; ff; d) := min
G2G(n;d)
I ff (G) (2.1)
and the (global) minimax interference level
G2G(n;d)
I
We first note restrictions on the parameter space. Since all graphs in G(n; d) have ndedges,
it follows that
n and d cannot both be odd : (2.3)
We restrict attention to the threshold range
because ff - nimplies that all colors interfere. Thus
Our first result concerns ' and L for degree 2.
Theorem 2.1. Let 2.
(a) For all
(b) For all fl - 3,
(c) If
This is proved in Section 3.
We now consider d in the range
for the minimum interference level '. The cases of are treated separately. We
obtain an almost complete answer for 2.
Theorem 2.2. Suppose that 2.
(a) If n is even, then
and
nis even, or nand d are both odd
and d is even :
(b) If n is odd, then
and
(c) If n is odd and in the remaining range n\Gamma2ff - d - n, then '(n; ff; d) - d. Furthermore:
there is an integer 2s
(ii) '(n; ff; d) - d
2 is even, and there is an integer 4s
Case (c) above is the only case not completely settled. Instances of it are illustrated in

Figure

2.1. The number beside each vertex clump gives the color assigned to those vertices, and
the number on a line between noninterfering clumps is the number of edges between them. Case
analyses, omitted here, show that no improvements are possible in part (c) of the theorem when
Given n - 21, (i) has three realizations, namely '(15; 5;
0, (ii) has only the realization at the bottom of Figure 2.1, and cases.

Figure

2.1 about here
We remark that the bounds on '(n; ff; d) for d ? n
are obtained using a variant of Turan's
theorem on extremal graphs (Tur'an, 1941; Bondy and Murty, 1976, p. 110). Theorem 2.2 is
proved in Section 4.
We now consider the minimum interference level ' when fl - 3. To handle this case we use
Theorem 1.1, which is proved in Section 5. Let p and q be the unique nonnegative integers
that satisfy
that is
c and
Our bounds for are given in the next two theorems for respectively,
and are proved in Section 6. The case is somewhat simpler.
Theorem 2.3. Suppose that fl - 3 and that fl divides n, i.e.
(a) If d -
(b) If d ?
is odd or if
even and p is even
even and p is odd :
Theorem 2.4 Suppose that fl - 3 and fl doesn't divide n, i.e. q - 1.
(a) If d
(b) If d -
where
even and p is even
even and p is odd :
We turn next to results for the minimax interference level L. We first distinguish cases
Theorem 2.5. Suppose that 3 - d - 2. Then:
(a) L(n; ff; d)
(b) L(n; ff; d) ? 0 for
The only cases in the parameter range 1 - ff - n\Gamma 1 and fl - 2 not settled by this theorem
are those with
Both occur in this exceptional case, e.g. for
Our final main result provides bounds for L. Set
c
and
In view of Theorem 2.5 we consider only the range that 2 - fl - d.
Theorem 2.6. Suppose that 3 - d -
and
In the special case that d can be written more simply as
nd
This applies in particular when which case the upper and lower bounds coincide,
yielding (1.1). If n is substantially larger than d, and d is somewhat larger than fl, then L is
closely approximated by nd
Theorems 2.5 and 2.6 are proved in Section 7.
3. Elementary Facts: Theorem 2.1
We derive general conditions that guarantee
graphs (Theorem 2.1).
Lemma 3.1. If 1 - ff ! n
(a) '(n; ff; d)
and
(b) '(n; ff; d)
2 and n is even: (3.2)
Proof. (a) Given d ng and consider the coloring
for every i. We construct a suitable G starting with the edge set
If n is odd, or if n is even and d is odd, let every vertex has degree d and
every edge has D ? ff, so '(n; ff; d) = 0. If n and d are both even, so ff - (n
ng
. Again, every
vertex has degree d and every edge has D ? ff, so '(n; ff; d) = 0.
(b) Let -G denote the chromatic number of the graph G. The definition implies that:
If n is even and d - n
d) contains a bipartite graph with n=2 vertices in each part,
so (b) follows from (3.3), since fl - 2. \Xi
We remark that the construction in part (a) uses all n colors, and when d
same construction gives many interfering edges. It is natural to consider the opposite extreme,
which is to use only a maximal set of
noninterfering colors. This leads to part (b).
The restriction in part (b) that n be even is crucial, because no d-regular bipartite graph
exists for odd n. Indeed there are exceptions where '(n; ff; d) ? 0 for some d ! n
2 with n odd:
see Theorems 2.1 and 2.2. These exceptions occur when but are not an issue for fl - 3.
We obtain bounds on the minimax interference level L using the following well-known
bound for the chromatic number -G of a graph G.
Proposition 3.1. For every finite simple graph G,
where \Delta G is the maximum degree of a vertex of G. Furthermore -G - \Delta G provided that no
connected component of G is an odd cycle or a complete graph.
Proof. Brooks (1941); Bondy and Murty (1976, pp. 118 and 122). \Xi
This result immediately yields the following condition for the minimax interference level
Lemma 3.2. If 1 - ff ! n
Proof. The definition of L(n; ff; d) gives
for a d-regular graph, (3.5) follows from Proposition 3.1 via (3.6). \Xi
Proof of Theorem 2.1. (a) Since follows from (3.2) if n is even, and from
if n is odd and ff - n
(b) follows from Lemma 3.2.
(c) Given every graph in G(n; 2) is a sum of vertex-disjoint cycles. Suppose
1. Then an even cycle has minimum interference 0, a 3-cycle has minimum
interference 1, and an odd cycle with five or more vertices has minimum interference 0 or 1.
It follows that
one 4-cycle), and L 2 2. The last case uses M \Gamma 1 3-cycles and one
5-cycle. When the 5-cycle's vertices are colored successively as 1, ff
ff, it has no interference if [n
so 1 in this case. More generally, suppose one vertex of the 5-cycle is colored 1.
Its neighbors must have colors in [ff to avoid interference. Then their uncolored
neighbors, which are adjacent, must have colors in [2ff to avoid
interference. This set has which is - ff if (2n \Gamma 4)=5 - ff.
Hence
4. Minimal Interference Level: Theorem 2.2
We prove Theorem 2.2 in this section. The ranges stated where '(n; ff; d) = 0 follow from
Lemma 3.1, so the main content of parts (a) and (b) of Theorem 2.2 concerns the values
'(n; ff; d) for d ? n
2 . To obtain these we use a variant of Tur'an's theorem (Tur'an, 1941; Bondy
and Murty, 1976, p. 110), which we state as a lemma. An application of the lemma at the
end of the section yields the exact value of L(n; ff; well as '(n; ff; 1). Recall that
an equi-t-partition of a vertex set V is a partition fV
Lemma 4.1. The maximum number of noninterfering edges in the complete graph K n with
vertex set V and threshold parameter ff is attained only by a coloring [n] that has
are in different parts of an equi-fl-partition of V .
Proof. Suppose that a coloring f of the complete graph K n has f i vertices of color i
ab denote the number of vertices of
colors other than a and b that interfere with a and not b. If all color-i vertices are recolored
j, the net increase in interference is f i (m vertices are recolored i, the
net increase in interference if f Hence at least one of the recolorings does not
increase interference. Continuing this recoloring process implies that noninterference in K n is
maximized by a fl-partite partition of V such that D(f(x); f(y)) ? ff whenever x and y are in
different parts of the partition. Tur'an's theorem then implies that maximum noninterference
obtains only when the partition is an equi-fl-partition. \Xi
We can assume without loss of generality that the coloring f found in Lemma 4.1 is constant
on each part of an equi-fl-partition, with f(V flg. If
interfering edges are then dropped from K n , we obtain a complete equi-fl-partite graph with
zero interference and chromatic number fl. This graph is regular if and only if fl divides n and
each part of the partition has n=fl vertices.
Proof of Theorem 2.2. Throughout this proof
We consider first (a) and (b). The ranges given where '(n; ff; d) = 0 come from Lemma 3.1.
So assume now that d ? n
. Let G 0 be a complete bipartite graph fA; Bg such that
Lemma 4.1 implies that two-coloring G 0 using noninterfering colors for A and B uniquely
maximizes the number of edges with no interference when 2. Therefore ' - nd=2 \Gamma jAjjBj .
(a) Suppose n is even. If n=2 and d are odd, the number of edges needed within each part
of G 0 to increase all degrees to d is (n=2)(d \Gamma n=2)=2, which is an integer since d \Gamma n=2 is even.
It follows that if n=2 is even, or if n=2 and d are odd, then
If instead n=2 is odd, and d is even, then (n=2)(d \Gamma n=2) is odd, G 0 is not part of any
graph in G(n; d), and ' ? replacing G 0 with
a complete bipartite graph G 1 with bipartition fA
Beginning with G 1 , each vertex in A 0 requires more degrees to have degree d, and
each vertex in B 0 requires edges added to have degree d. Both d
and are even, so edge additions as needed can be made within A 0 and B 0 to obtain
1 in this case; and (2.9)
is proved.
(b) Suppose n is odd, so d is even by (2.3). Beginning with G 0 , each of the (n
vertices in A requires d \Gamma (n \Gamma 1)=2 more incident edges added to have degree d, and each of the
incident edges added to have degree d. Each
of f(n contains an even integer, so we can
make the required additions of edges within A and B. Hence
It remains to prove (c), which has three parts (i)-(iii). Assume henceforth that n is odd
even because n is odd. Augmented equi-bipartite graphs,
illustrated at the top of Figure 2.1, show that ' - d=2 since they require d=2 edges within the
1)=2-vertex part to obtain degree d for every vertex. Sometimes case in point
is the largest possible ff for
Suppose 1g. Each vertex in the
color set [n] has exactly two others for which D ? ff, and the graph of noninterfering colors is
an n-cycle whose successive colors are 1)=2. If every color
were assigned to some vertex in G 2 G(n; d), there would be at least n(d \Gamma 2)=2 interference
edges. But n(d must avoid at least one color to attain '. Deletion of one
color from the n-cycle of noninterfering colors breaks the cycle and leaves the noninterference
graph
Because all x i colors interfere with each other, and all y i colors interfere with each other, we
can presume that f uses only one x i and an adjacent y j . This yields the augmented bipartite
structure of the preceding paragraph, and it follows from maximization of between-parts edges
that This completes the proof of (iii).
For (i) and (ii), assume ff ! (n \Gamma 3)=2 and consider an odd r - 5 sequence of colors c 1 ,
1. The tightest such sequence
has to color
k. It follows that the final color c r can be chosen not to interfere with c
i.e., if
We usually consider the smallest such odd r - 5 because this allows the
the largest d values. Our approach, illustrated on the lower part of Figure 2.1, is to assign
clumps of vertices to the c i in such a way that all edges for G 2 G(n; d) are between adjacent
clumps on the noninterference color cycle c
Suppose (4:2) holds for a fixed odd r - 5. We assume that r ! n because the ensuing
analysis requires this for d - 3. Let a and b be nonnegative integers that satisfy
We prove (i), then conclude with (ii). The analysis for (i) splits into three cases depending on
the parity of a and br=4c.
Case 1: a odd
Case 2: a even, br=4c odd
Case 3: a even, br=4c even.
Because n is odd, Case 1 requires b to be even and Cases 2 and 3 require b to be odd.
Case 1. Given an odd a, we partition the n vertices into b clumps of a vertices each
clumps of a vertices each. The clumps are assigned to colors in the noninterference
cycle so that the clumps of each type are contiguous. Cases for
are illustrated at the top of Figure 4.1. We begin at the central (top) a clump and proceed
symmetrically in both directions around the color cycle, assigning between-clumps edges as
we go so that all vertices end up with degree 2a. The required edges into the next clump
encountered are distributed as equally as possible to the vertices in that clump. When we get
into the clumps with a+ 1 vertices, the number of between-clumps edges needed will generally
be less than the maximum possible number of (a . Numbers of between-clumps edges
used to get degree 2a for every vertex are shown on the noninterference lines between the c i
on

Figure

4.1.

Figure

4.1 about here
The preceding construction yields '(n; ff; d) = 0 for even d is less
than 2a, say we modify the procedure by using fewer between-clumps
edges for the required vertex degrees: clump sizes are unchanged. Because n=r
yields the contradiction that n ! ra, it follows for Case 1 that
Case 2. With a even and br=4c odd, we have b odd and r 2 f5; 7; 13; 15; :g. In this
case we assign a \Gamma 1 vertices to c 1 and proceed in each direction around the c i cycle, assigning
a, a vertices to the next (r \Gamma 1)=2 c i in order. The
penultimate number a 0 equals a if r 2 f5; 13; and is a :g. The
ultimate number a   in chosen so that there are [n \Gamma (a \Gamma 1)]=2 vertices (excluding the a \Gamma 1 for
1 ) on each side of the color cycle. If a
a  1)=2. The two cases are shown on the lower left of Figure 4.1 with numbers of
between-clumps edges that give degree d = 2a for every vertex. If even d is less than 2a, fewer
edges are used, as needed, down the two sides. As in Case 1, we get
Case 3. With a even and br=4c even, we have b odd and r 2 f9; 11; 17; 19; 25;
Here we assign a+ 1 vertices to c 1 and proceed with a, a \Gamma 1, a, a+ 1, a, a \Gamma 1, a, a+
a   vertices assigned to the next (r \Gamma 1)=2 c i in each direction away from c 1 . We get a
and a
:g. The two cases are shown on the lower right of Figure 4.1. As before,
if d - (2=r)n.
This completes the proof of (i), after defining s by 1. We have also checked that
the construction used here cannot yield unless the conditions of (i) hold.
There is however one other set of circumstances where this construction yields a value of
r n, and these circumstances are exactly the hypotheses of (ii), namely:?
d - 8; d=2 is even
is odd since d=2 is even)
In this case we partition the vertices into (r +1)=2 clumps of vertices each and (r \Gamma 1)=2
clumps of d=2 The clumps are arranged
around the noninterference color cycle c 1 , c
We use all possible between-clumps edges. This gives degree d for every
vertex except those in the c 2 clump, which has incoming edges
from c 1 and c 3 . The degree total for c 2 should be d, so we need to add
to get degree d for each c 2 vertex. Prior to the additions,
each c 2 vertex has degree d \Gamma 2 by our equalization construction, so the additions can be made
by a complete cycle within the clump. It follows that ' - d=2 \Gamma 1, proving (ii). \Xi
We conclude this section by noting that the modified Tur'an's theorem (Lemma 4.1) easily
allows us to completely settle the case of degree
Corollary 4.2. For
c
Proof. Write
so
An equi-fl-partition of an n vertex set has? !
q parts, each with
each with p vertices.
Now the unique graph G 2 G(n; applying Lemma 4.1, we have
p!
which is (4.4). \Xi
5. Chromatic Number Bound: Theorem 1.1
This section gives a self-contained proof of Theorem 1.1. We first recall two preliminary
facts, stated as propositions.
Proposition 5.1. (Dirac (1942)) Let G be a simple graph. If every vertex of G is of degree
at least jV (G)j=2, then G is Hamiltonian, that is, G has a cycle of length jV (G)j.
Proof. See Bondy and Murty (1976), p. 54. \Xi
Recall that a matching in a simple graph G is a subset of mutually vertex-disjoint edges of
G. A matching is perfect if every vertex in G is on some edge of the matching. The following
is a consequence of a well-known theorem of Hall (1935).
Proposition 5.2. (Marriage Theorem) If G is a d-regular bipartite graph with d ? 0, then
G has a perfect matching.
Proof. See Bondy and Murty (1976), p. 73. \Xi
We study the function OE(n; d; r) defined by
1 if there exists an n-vertex d-regular r-colorable graph,
When OE(n; d; denote such a d-regular r-colorable (that is, r-partite)
graph having n vertices. We consider only values in which nd is even.
Our first observation is that because an r-colorable graph is also (r + 1)-colorable,
The purpose of the next two lemmas is to prove that OE(n; d; r) is monotone when r - 3 is
held fixed and d varies over values where nd is even.
Lemma 5.1 (a) If d - nand if either r - 3 or
(b) If d - n
If in addition n is even, then
Proof. (a) Suppose that n is even. The inequality (5.1) implies that it is enough to show
OE(n; d;
We use reverse induction on d - n=2. For the base case the complete equi-2-partite
graph gives OE(n; n=2; 1. For the induction step, suppose we know that OE(n; d;
a d-regular bipartite graph G(n; d; 2) exists, and by Proposition 5.2 it has a perfect matching
M . Remove all edges in M from G to obtain a (d \Gamma 1)-regular bipartite graph G(n; d \Gamma
Hence OE(n; d \Gamma
Suppose n is odd. Then (5.1) implies that it is enough to show
OE(n; d;
Now d must be even by (2.3), and d - (n \Gamma 1)=2. Because
by (5.5). Consider G := G(n \Gamma 5.2 we may find a
perfect matching of G, say
from G the edges and add to G a new vertex z and the edges fz; x i g and
it is easy to see that the resulting graph is a d-regular 3-partite
graph with n vertices, which proves (5.6).
(b) Let G = G(n; d; r), which exists by hypothesis. Since d - n, Proposition 5.1 guarantees
that G has a Hamilton cycle C. Removing all edges from C yields a G(n; d \Gamma 2; r), so OE(n; d \Gamma
1. If moreover n is even, then C has even length and we get a perfect matching M
by taking alternate edges in C. Removing all edges in M from G yields a G(n; d \Gamma 1; r), so
1 in this case. \Xi
Lemma 5.2. If r - 3, then
provided that nd 1 and nd 2 are both even.
Proof. Suppose
are done.
Suppose used inductively on decreasing d gives
For odd n, since nd 1 and nd 2 are both even, both d 1 and d 2 must be even. Now Lemma 5.1(b)
gives
so (5.7) follows. \Xi
Proof of Theorem 1.1. To commence the proof, we define p and q by
that is
r c - 1. Note that r divides only if In terms of p and q the
assertions of the theorem then become:
(i) If
(iii) If 2.
To prove (i)-(iii), we use the complete equi-r-partite graph G r (n) defined as follows. The
graph G r (n) has vertices we define the vertex sets
The edge set of G r (n) is
E(G r
Here is an equi-r-partition of V with
For 1 - a - b - r we let G r
a;b denote the induced subgraph of G r (n) on the vertex set
To prove (i), if is an (n \Gamma p)-regular graph, hence
Lemma 5.2 implies OE(n; d;
To prove (ii), let
q+1;r . Then (5.10) shows that H is a p(r \Gamma q \Gamma 1)-regular graph
having vertices. Now r \Gamma q - 2 implies that H has degree p(r \Gamma q \Gamma 1), which is greater
than half its vertices, so H has a Hamilton cycle C by Proposition 5.1.
If p(r \Gamma q) is even, then H has a perfect matching M obtained by taking every other edge
in C. Removing all edges in M from G r (n), the resulting graph is (n
then completes the proof of (ii).
If p(r \Gamma q) is odd, then p is odd, hence so is
by (2.3). Thus it suffices to show that
this case, for then Lemma 5.2 gives OE(n; d; 2.
1;q . Then H 0 is a (p vertices. If q ? 1
then
hence H 0 is Hamiltonian. Since (p + 1)q is even, H 0 has a perfect matching M 0 . Removing all
edges in M 0 [C from G r (n), the resulting graph is (n
Suppose 1. Notice that since p(r \Gamma 1) is odd, r 6= 3, hence r - 4. Let H 00 be the
induced subgraph of G r (n) on the set
r
and
Then the number of vertices of H 00 is p(r and the minimum degree of H 00 is
Proposition 5.1 implies that H 00 has a Hamiltonian cycle C 00 . By removing all edges in C 00 [E
from G r (n) we have an (n
To prove (iii) we proceed by induction on r, with an induction step from r to r 2. There
are two base cases,
Base Case r = 3. We have 2. Let
Consider the graph G obtained by removing from G 3 (n) all edges in g.
Then it is easy to see that G is (n
gives OE(n; d; 2.
Base Case 4. We have 3. Suppose first that p is odd. We relabel
the vertices of G 4 (n) so that the sets X j in (5.9) become
Let H be the subgraph of G 4 (n) induced on the vertex set fw 3g. Then
even and H is Hamiltonian. Thus H has a perfect matching, call it M .
Consider the edge set
and form a graph G by removing all edges in E [ M from G 4 (n). Then G is an (n
regular subgraph of G 4 (n), hence OE(n;
Lemma 5.2.
Suppose now that p is even. Then
is forbidden by (2.3). It suffices therefore to show that OE(n; this case, for
then Lemma 5.2 gives OE(n; d; 2. We use
the vertex labelling (5.12), and let H be the subgraph of G 4 (n) induced on fw 3pg.
Then jV so H has a perfect matching M . Consider
the edge set
Form a graph G by removing (n). It is an (n
Induction Step. Fix r - 5 and define
nd is eveng ;
so 3. It is enough to show that OE(n; d
yields OE(n; d;
To do this, set
furthermore we
easily check that
We may apply the induction hypothesis at r
to conclude that there exists a d 0 -regular (r \Gamma 2)-partite graph
a d 1 -regular bipartite graph with 2(p vertices disjoint from those of G; such a graph H
exists by Lemma 5.1(a). Take the disjoint union of G and H and add in all edges between
V (G) and V (H) to obtain a new graph G 0 on n vertices which is d 0 (n; r)-regular, according to
(5.13). Thus OE(n; d completing the induction step for (iii). \Xi
6. Minimal Interference Level: Theorems 2.3 and 2.4
In this section we study the range fl - 3 and prove Theorems 2.3 and 2.4. The cases where
'(n; ff; d) = 0, i.e. for d smaller than about follow from Theorem 1.1 applied with
For the remaining cases, the harder step in the proofs is obtaining the (exact) lower bounds
for '(n; ff; d). The upper bounds are obtained by explicit construction.
We proceed to derive a lower bound for '(n; ff; d) stated as Lemma 6.2 below. Let G be
any d-regular graph on n-vertices, let ng be a given coloring of G, and
let ff also be given. We begin by partitioning the n colors into fl groups f ~
that each group ~
A i consists of consecutive colors and the groups ~
A fl are themselves
consecutively arranged with respect to the cyclic ordering of colors (mod n), with all groups
but ~
A 1 containing exactly ff
A 1 contains the remaining ff
m is given by
and such a partition is completely determined by the choice of ~
We now choose ~
A 1 so as to minimize the number of vertices v in G that are assigned colors
f(v) in ~
A 1 . After doing this, we have the freedom to cyclically relabel the colors (via the map
affecting which edges have vertex colors that interfere. We use
this freedom to specify that
~
in which case
~
see

Figure

6.1. Notice that for 2 - i - fl any two colors in ~
A i interfere with each other.

Figure

6.1 about here
This partition of the colors induces a corresponding partition of the vertices of G into the
color classes
Now set
a
We now count the edges in G and in its complement -
various ways. For any
two subsets V and W of vertices, let e(V; W ) count the number of edges between vertices in V
and those in W , and let -
count the number of edges between A i and
A j that are not in G, which is
-a i;j := a i a
Along with this we define
a
The d-regularity of G then yields
a
The potential interfering edge set B i;j between vertices in A i and those in A j is
The actual interfering edge set is and we set
c i;j :=
We clearly have
- a i;j
Finally, let ffi   and ffi count the potential and actual non-interfering edges in A 1 , respectively,
i.e.
Certainly ffi   - ffi. Since all edges between the vertices in the same component A i interfere,
except for ffi edges in A 1 , we obtain the bound
I ff G;
To bound this further, we need the following bounds for edges connecting a vertex in the color
set ~
A 1 to a vertex in its two neighboring color sets ~
A 2 and ~
A fl .
Lemma 6.1. We have
and
Proof. We start with (6.6). By (6.4) it is enough to show that
It suffices to show for fixed v 2 A 1 with ff
because, using ff - m, this implies that, for sums over v 2 A 1 with ff
To prove (6.8), given v 2 A 1 with ff we define the vertex set
This is a set of ff by the minimizing property of
the color set ~
A 1 . Now ff implies that
Thus
which is exactly (6.8). Thus (6.6) follows.
The proof of (6.7) is analogous. \Xi
To state the lower bound lemma, recall that the quantities p and q are defined by
so
Lemma 6.2. If d -
Proof. We derive this result from the general bound
I ff (G; f) - \Sigma fl
where a for the vertex partition (6.2). To establish (6.10), we first note that Lemma 6.1
Together with (6.3), this yields
Since the left side of this inequality is an integer,
However, (6.3) also gives
Substituting these bounds in (6.5) yields (6.10).
To derive (6.9), we minimize the right side of (6.10) over all possible values: a i - 0 subject
to \Sigma fl
It is easy to verify that this occurs when all the a i 's are as equal as possible,
i.e. 8
q of the a i take the value
of the a i take the value
Thus
I ff (G; f) - qd(p
which gives (6.9). \Xi
Proof of Theorem 2.3. (a) This bound follows from Theorem 1.1, taking noting
that
(b) For d ? first establish the lower bounds
where
is odd or if n \Gamma d is even
and p is even;
even and p is odd ;
using Lemma 6.2. The case simplifies to
Now (6.12) follows on determining the cases for which p(d
To show that this bound is attained, we simply construct the graph G with the coloring f
that makes (6.11) hold. The constructions are easy and are left to the reader. \Xi
Proof of Theorem 2.4. (a) The bounds where '(n; ff; d) = 0 follow from Theorem 1.1
with
There remains the case in which
(where Theorem 1.1 does not apply). We must show that
For the upper bound ' - p, it suffices to construct an appropriate graph. Note first that p
must be even since if p is odd then
is also odd, contradicting (2.3). Now consider the equi-fl-partite graph G fl (n) defined in the
proof of Theorem 1.1. We take a perfect matching M from the induced subgraph of G fl (n)
on the vertex set (X fl We remove all the edges in M from G fl (n) and add
the edges g. Then it is straightforward to
check that the resulting graph G is (n 1)-regular and it clearly has exactly pinterfering
edges when the sets X i are colored with fl mutually noninterfering colors.
To show the lower bound ' - p
G be an (n f an n-coloring
of V (G) such that
I ff (G;
Take the partition fA associated to f constructed at the beginning of
this section. We consider cases.
Case (i). a 1 2.
The minimality property of A 1 implies that, for all
(G)nfvg such that jf(v) \Gamma f(w)j - ff.
Thus I ff (G; f) - n=2 ? p=2.
Case (ii). a
Here the equality in (6.5) combined with
I ff (G; f) - \Sigma fl
Using (6.3) we then have
I ff (G; f) -
Case (iii). All a
case requires that of the a i equal one a i equals p.
Suppose first that a p. Observe that (6.14) and (6.3) yield
I ff (G; f) - \Sigma fl
Now (6.2) and a
a
Substituting this in (6.15) gives I ff (G; f) - pSuppose finally that a only one a
a both. We treat only the case that a since the argument for a
is similar. Let a i 0
p. Now by (6.5) and (6.3)
I ff (G; f) - 1
a i
Lemma 6.1 gives -a 1;2
I ff (G; f) - 1
completing case (iii).
(b) We start from the formula (6.9) of Lemma 6.2, which gives a lower bound. We claim
that equality occurs. This formula of '(n; ff; d) splits into several cases, according to when
are integers or half-integers, and consideration of
the parities of n \Gamma d and p leads to the formulas for ' in (2.12).
For the upper bound, obtaining equality in the formula for '(n; ff; d) requires (6.11) to hold,
and this easily determines the construction of a suitable graph G and a coloring f . We omit
the details. \Xi
7. Minimax Interference Level: Theorems 2.5 and 2.6
We conclude by proving the bounds for L(n; ff; d) stated in Section 2.
Proof of Theorem 2.5. To show part (a), the condition L(n; ff; d) certainly holds
if the chromatic number -G - fl for all G 2 G(n; d). This holds for fl ? d by Brooks' theorem
(Proposition 3.1). For the case we use the strong version of Brooks' theorem, which
states that -G - \Delta G if no component of G is an odd cycle or a complete subgraph. Here
d, and d - 3 implies there are no odd cycles, while the condition
any connected component being the complete subgraph K d , for any other components must
be d-regular but have at most d vertices, a contradiction.
To show part (b), suppose that n - 2(d 1). Let G 2 G(n; d) consist of a complete graph
K d+1 plus a d-regular graph G 0 on the other vertices. If d is odd then n is
even, so that even, and the existence of G 0 is assured by a theorem of Erd-os and
Gallai (1960) for simple graphs with specified degree sequences. If fl - d, at least two vertices
of K d+1 interfere, so L ? 0.
Suppose that 1. This implies d - 2a because we presume that
2. Let G consist of two disjoint copies of K d+1\Gammaa , adding edges between them that
increase every degree to d. Each vertex requires a such edges, and this is feasible because
a, at least two vertices of K d+1\Gammaa interfere, so L ? 0.
Suppose finally that 1. Then n is odd, so d must be even.
consist of two disjoint graphs G
additions and deletions as follows. Add a edges from each G 1
vertex to G 2 vertices in as equal a way as possible for resulting vertex degrees in G 2 . Then
each vertex in G 1 has degree d, x vertices in G 2 have degree d + 1, and y vertices in G 2 have
degree d, where
These equations imply that so x is even. We then remove x=2 edges within
so that all vertices have degree d. We thus arrive at a graph G 2 G(n; d). If fl - d \Gamma a then
at least two vertices in G 1 interfere, so L ? 0. Thus part (b) holds. \Xi
Proof of Theorem 2.6. Suppose that 3 - d -
W be nonnegative integers that satisfy
To derive the upper bound on L in Theorem 2.6, let G be any graph in G(n; d). Let S
denote the family of all partitions of the vertex set of G into fl groups, with q groups of size
groups of size p. We adopt a probability model for S that assigns probability
1=jSj to each partition. Whichever partition obtains, we use fl mutually noninterfering colors
for the fl groups in the partition. Suppose fu; vg is an edge in G. The probability that u and
v lie in the same part of a member of S, so that fu; vg is an interference edge, is
The expected number E[I ] of interference edges is nd=2 times this amount, i.e.,
so some member of S has a coloring that gives less than or equal to E[I ] edges whose vertices
interfere. This is true for every G 2 G(n; d). Therefore we get the upper bound
For the lower bound, assume initially that (d
Let G consist of U disjoint copies of K d+1 . Then L(n; ff; d) - UL(d
is the minimum number of interfering edges in K d+1 for an [n]. The analysis in
Lemma 4.1 shows that L(d + 1; ff) is attained by an equi-fl-partition of V d+1 with f constant
in each part. Since an equi-fl-partition of V d+1 has!
Q groups of
of P vertices each,
we have
To
form G we begin with U disjoint copies of K d+1 and a disjoint KW . Each vertex in KW needs
incident edges, so we add a total of W (d
the K d+1 in such a way that W (d edges can be removed from within the K d+1 to
end up with degree d for every vertex. Note that W (d
and d would be odd. We ignore possible interference within KW and allow for the possibility
that every edge removed from the K d+1 is an interference edge to get the lower bound



--R


On sublattices of the hexagonal lattice
Graph Theory with Applications

On coloring the nodes of a network

Some theorems on abstract graphs
Graphs with prescribed degrees of vertices (in Hungarian)
The channel assignment problem for mutually adjacent sites

Pair labellings of graphs
theory and application
On representatives of subsets
Graph homomorphisms and the channel assignment problem
Further results on T



An extremal problem in graph theory (in Hungarian)

--TR
graph coloring;interference threshold;regular graph