Given a graph = (, ) of maximum degree Δ, denoting by (, ) the distance in between nodes , ∈ , an (3, 2, 1)-labeling of is an assignment from to the set of non-negative integers such that |() − ()| ≥ 3 if and are adjacent, |() − ()| ≥ 2 if (, ) = 2, and |() − ()| ≥ 1 if (, ) = 3, for all and in . The (3, 2, 1)-number () is the smallest positive integer such that admits an (3, 2, 1)-labeling with labels from {0, 1, . . . , ()}. In this paper, the (3, 2, 1)-number of certain planar graphs is determined, proving that it is linear in Δ, although the general upper bound for the (3, 2, 1)-number of planar graphs is quadratic in Δ.
In practice, interference among frequencies could go beyond distance two so, in 2004, Liu
and Shao [17] generalized the (
Since its definition, the technology has changed, and the (
The problem of deciding whether () is upper bounded by a given parameter is trivially
NP-complete because, for example, it coincides with the decisional version of the (
In general, if is a graph with maximum degree Δ, Clipperton et al. [8] proved that () ≤ Δ3 + Δ2 + 3Δ; later, this upper bound was improved to Δ3 + 2Δ [7].
The (
Liu and Shao [17] showed that () ≤ 15(Δ2 − Δ + 1) if is a planar graph of maximum degree Δ.
Nevertheless, for interesting subclasses of planar graphs, better results are known:
• -length paths and cycles , ≥ 8: () = 3Δ + 1 = 7, () = 3Δ + 1 = 7 if
is even and = 3Δ + 2 = 8 if odd (but also the results for small values of are found)
[8];
• ladders = × 2: () = 2Δ + 3 = 9 if ≥ 5 (but also the results for small
values of are found) [7];
• caterpillars : () ≤ 2Δ + 2 [8];
• trees : 2Δ + 1 ≤ ( ) ≤ 2Δ + 3, deciding which is the exact value for the (
It is evident that, despite the general quadratic upper bound, for some classes of planar graphs, the upper bound on () is linear in Δ. We will prove this is true also for other important subclasses of planar graphs, i.e., regular grids, the square of cycles, and outerplanar graphs.
Given a graph = (, ), we denote by the number of its nodes and by the number of its
edges. For each ∈ , () represents the degree of , and Δ is the maximum degree of .
Definition 1. Let = (, ) be a graph and be a mapping : → N ∪ {0}. is an
(
2, i (, ) = 2
⎪⎩1, i (, ) = 3
Definition 2. Given a graph = (, ) and an (
It is not restrictive to assume that, given a graph , there exists a node of such that () = 0, otherwise it is possible to obtain a new labeling with this property by shifting the values of all the labels from () to () − min∈ () for each ∈ .
This concept has been introduced in [15] concerning another labeling function, the (
Given a graph , the values of (), for any ∈ , are interchangeably called labels and
colors. Because of this name, it is common to define palette of an (
For each graph , it holds the symmetry property of the palette: it is always possible to get a new labeling ′ starting from a given one by simply assigning ′() = (, ) − (); trivially, (, ) = (′, ).
Given an (
In this paper, we consider the following subclasses of planar graphs.
The infinite hexagonal grid is the graph naturally derived from a tassellation of the plane with regular hexagons. Since it is a regular graph of degree 3, we will name it 3. For the sake of completeness, we analogously define the infinite squared and triangular grids as derived from a tassellation of the plane with squares and equilateral triangles, respectively, which are regular graphs of degree 4 and 6, and hence denoted 4 and 6. Finally, it is also possible to generalize the concept of regular grid to not planar graphs and define the infinite octagonal grid , which does not come from any tassellation but is a regular graph of degree 8, call it 8.
A cycle is an ordered sequence of nodes 1, . . . , connected by edges {, +1}, = 1, . . . , − 1, and {, 1}. denotes an node cycle.
The square of a graph is a graph 2 that has the same set of nodes as , and two nods are adjacent when their distance in is at most 2. We focus on the square of cycles 2, which are planar graphs when is even and when = 3.
A graph is outerplanar if it can be embedded in the plane so that every node lies on the boundary of the outer face. It follows that once the first node has been chosen, clockwise order around this face induces a total order on the graph nodes.
We now present some preliminary results that will be exploited in the following, although are of their own interest.
Theorem 1. For any graph with maximum degree Δ ≥ 2, () ≥ 2Δ + 1. Proof. This lower bound trivially comes from observing that the Δ neighbors of a maximum degree node must be labeled with Δ labels at mutual distance 2 (so at least 2Δ − 1 colors) and that must receive a diferent label at a distance 3 from any one of its neighbors. So, at least 2Δ + 2 colors are necessary. □
A fan has + 1 nodes; of them, called 1, . . . , , constitute a path, while one, called , is connected by an edge to all the other .
Murugan and Surija [18] proved that, for ≥ 5, () = 2 + 1. Here we complete this result also for small values of : Lemma 1. () = 2 + 1 if ≥ 4 while () = 2 + 2 if = 2, 3.
Proof. First, observe that a possible general labeling of assigns to label 0, and ordinately from left to right the following sequence of labels to 1, . . . , : it starts with color 3 and hops colors 4 by 4; when the end of the palette is reached, it begins again from color 5 and hops again 4 colors by 4. (For example, if = 5, 1, . . . , 5 will be labeled by labels 3, 7, 11, 5, 9 in this order.) If = 2, is a triangle, all three nodes must get labels at mutual distance 3, i.e., 0, 3, and 6. Hence (2) = 2 + 2 = 6.
If = 3, we prove that (3) = 8.
First we prove that (3) > 7. By contradiction, assume that the palette = {0, 1, . . . , 7}. If () = 0, then 1, 2 and 3 must necessarily be labeled with 3, 5, 7 in some order; but no one among these three colors is suitable to be the label of 2, that is adjacent both to 1 and to 3. If () = 7, similar reasonings hold. If finally, is labeled with a color diferent both from 0 and from 7, it is easy to see that there are not three available labels at mutual distance 2.
On the other hand, (3) ≤ 8 because a possible feasible labeling of this graph assigns 0 to node and the labels 6, 3, 8 to 1, 2, 3.
So, (3) = 2 + 2 = 8.
If = 4, we apply Theorem 1, deducing that (4) ≥ 9. A possible labeling assigns 0 to node and the sequence 7, 3, 9, 5 to 1, . . . , 4 in this order. It follows that (4) = 2 + 1 = 9. (Note that the labeling procedure used for ≥ 5 would produce for 1, . . . , 4 the sequence 3, 7, 5, 9 that is not feasible because colors 5 and 7 are assigned to adjacent nodes.) □
Since we want to exploit a feasible (
Theorem 2. Let be given a fan whose node has been pre-colored with label (). Then,
the (
Proof. We provide an (
Assume ≥ 5, first. In the reasonings under the proof of the previous lemma, colors 3, 4,
. . . , 2 + 1 were available and suficient for labeling 1, . . . , . If, instead of having 2 − 1
(i.e., 2 + 1 + 1 − 3) consecutive colors, we have the same number of colors possibly not
consecutive (because the colors around () are forbidden), a fortiori they will be suficient for
(
So, consider palette = {0, 1, . . . , 2 + 3} and remove from it colors () − 2, () − 1, (),
() + 1, and () + 2 whenever they are in because these are all the colors that cannot be
used to label 1, . . . . At least + 4 − 5 colors remain available for 1, . . . , , that are all
at mutual distance 2 via . Hence, the procedure that starts from the first available color and
then hops 4 by 4 on the colors remaining in after removing () and the colors too close to it
produces a feasible (
The equality holds given reasonings analogous to those used to justify Lemma 1, together with the hypothesis that () eliminates from the palette exactly 5 colors.
If ≤ 4, the reasoning is the same, but the labeling is diferent. We omit the details here not to overburden the exposition, but they can be easily deduced from the proof of the previous lemma. □
We conclude this section by giving some general lower bounds that, besides being of interest in itself, will be exploited when dealing with the considered subclasses of planar graphs. Theorem 3. For any graph with maximum degree Δ ≥ 2, if a maximum degree node with two neighbors of degree Δ exists, then () ≥ 2Δ + 2.
Proof. Let be the node of degree Δ, and and the nodes adjacent to and of degree Δ, too.
Consider a labeling function for , and particularly the label () assigned to . If () is diferent from 0, 1, () − 1 and (), then the label of excludes 5 labels from the palette used to label all its neighbors; each one of the Δ ’s neighbors have a diferent color, and these must be at a mutual distance of two; since () could lay between two colors assigned to two of the ’s neighbors, the number of used colors cannot be less than Δ + Δ − 2 + 5, obtaining () ≥ 2Δ + 2.
If, on the contrary, the label assigned to belongs to {0, 1, () − 1, ()}, then consider node . If the label assigned to is diferent from 0, 1, () − 1 and (), repeat the previous reasoning, getting () ≥ 2Δ + 2; otherwise, since both and are nodes at a distance two from with labels in {0, 1, () − 1, ()}, then necessarily has a label outside this set. Hence, repeat the previous reasoning on . □
It is known that (4) = 2Δ + 3 = 11 [7] and (8) = 23 [4]; more recently, it has been
proved that (6) = 19 [9]. So, in the following, we study the remaining grid 3, closing the
problem of (
Theorem 4. (3) = 2Δ + 3 = 9.
Proof. We first prove that (3) ≥ 9. Preliminarily, observe that 3 satisfies the hypothesis of Theorem 3 implying only (3) ≥ 2Δ + 2 = 8, that is not enough, so we proceed diferently.
Assume by contradiction that (3) = 8. Consider an optimal labeling l of span (, 3) = (3). Pick a labeled () = 0. Then, in order to remain inside the palette {0, . . . , 8}, there must be one neighbor ′ of labeled (′) ∈ {3, 4}. We consider the two cases separately.
Case 1: if (′) = 4, it is not possible to assign 3 labels at a mutual distance of at least two to the three neighbors of ′.
Case 2: if (′) = 3, the three neighbors of ′ must have labels 0, 6, and 8. So, there is a neighbor ′′ of ′ such that (′′) = 6, but it is not possible to assign 3 labels at a mutual distance of at least two to the three neighbors of ′′. It follows that in any case (3) ≥ 9.
Now, we provide a feasible (
We exploit the general technique introduced in [6], consisting in labeling one hexagon and then shifting this labeling, adding a coeficient mod 2Δ + 4.
bl f a e b d c
br bb i(a)i 1 3 5 8 0 -2 5 7 0 2 4 +2 i(b)i 7 9 1 4 6 +4 1 3 6 8 0
Refer to Fig. 1.a. To determine the labeling of a first hexagon and the coeficients , , and , shifting the labels toward the bottom, bottom-right and bottom-left, respectively, we call the nodes of a hexagon , , , , , and in this order; in view of the symmetry of the grid, it is not restrictive to assume that () = 0; moreover, it must hold: - () = () + = and () = () + ; - ( ) = () + and () = () + ; - () = () + = and () = ( ) + ; where the sums are mod 10.
Adding all the constraints required by the (
This method produces a labeling containing a pattern repeated along the grid; it is easy to
verify that it is a feasible (
It is worth noting that the above proof of the lower bound provides () ≥ 9 for every graph of minimum degree 3, including 3-regular graphs, that is a bound better than the ones given by Theorems 1 and 3.
The exact value of for cycles is known from [8]. Namely, when ≥ 8, () = 7 if is even, while () = 8 if is odd.
Here, we determine the (
Let us consider the small values of first.
If = 3, and 2 coincide with 3, and hence (2) = (3) = 3 − 3 = 6. When = 4 and = 5, 2 coincide with and again (2) = 3 − 3.
When = 6, each node and its neighbors induce in 2 a fan 4, from which we easily deduce (2) ≥ (4) = 10. Because of the generality of the choice of , we can apply Theorem 2 so having (62) ≥ 11. This lower bound is unfortunately not tight; indeed, (62) = 12. We omit the proof due to space reasons.
Lemma 2. (2) ≥ 12 when ≥ 7.
Proof. Preliminarily, observe that we can focus on 1 and its neighbors for simplicity: it is easy to shift the same reasonings on any other node of 2.
If assigns a color to 1, the same color cannot be assigned to another node if < 8
because 1 is at a distance ≤ 3 from for all < 8. Hence we need at least 7 diferent colors to
label the nodes of 2. Assume by contradiction that there exists a feasible (
Let (1) = 4. Then, its four neighbors (that are at a mutual distance of at least two) are forced to receive colors 7, 9, 11, and one between 0 and 1 in some order. We list all the possibilities: • if (2) = 9, then (3) is neither 7 nor 11 and will be either 0 or 1; is adjacent to both 1 and 2 so also () is neither 4 nor 7 nor 11 and can only be either 0 or 1; since 3 and are at distance 2, this configuration is unfeasible; • if (3) = 9, then (2) is neither 7 nor 11, so it must be either 0 or 1; in this way, colors 7 and 11 will be assigned to and − 1 in some order. In both cases, (− 2) is necessarily equal to 2 (if (2) = 0, indeed if (− 2) = 1, no possibility remains for (− 2)); no available colors are for (− 3). • analogously, we discard the possibilities of assigning color 9 to either − 1 or because of the symmetry between 2, 3 and , − 1 w.r.t. 1.
Given the possibility of shifting 1 in any position of 2, we conclude that label 4 cannot be assigned to any node.
Let now (1) = 9. Then, its four neighbors are forced to receive colors 0, 2, 4, and 6 in some order. Nevertheless, label 4 has already been excluded, so it is impossible to conclude a feasible labeling. Hence, label 9 cannot be assigned to any node.
If (1) = 6, then its four neighbors are forced to receive colors 9, 11, one between 0 and 1, and one between 2 and 3. But we already know that 9 cannot be assigned to any node, so also label 6 leads to an unfeasible situation and hence cannot be assigned to any node.
Given the symmetry of the palette, it follows that also colors (, 2)− 9 = 2, (, 2)− 6 = 5,
and (, 2) − 4 = 7 cannot be assigned to any node; otherwise, we could start from a feasible
(
In view of the previous reasonings, if it were (2) ≤ 11, the remaining colors would be only six (i.e., 0, 1, 3, 8, 10 and 11) and hence not enough, implying a contradiction, hence (2) ≥ 12. □
The previous lower bound is tight in some cases, as shown in the following result. Nevertheless, there are some values of n for which more colors are necessary (see Lemma 4). Lemma 3. (2) = 12 when ≡ 0 mod 7.
Proof. The lower bound comes from Lemma 2, while the upper bound derives from the following labeling:
(7+1) = 0, (7+2) = 4, (7+3) = 8, (7+4) = 12, (7+5) = 2, (7+6) = 6, (7+7) = 10, for each = 0, . . . 7 − 1. It is immediate to check its feasibility.
Lemma 4. (121) = 15 and (122) = 16.
Proof. To prove the lower bound, observe that both 121 and 122 are diameter 3 graphs, so every node must receive a diferent color. W.l.o.g., let (1) be a color in {0, . . . , (, 2) − 2}, = 11, 12. Only 6, 7 and 8 are at distance 3 from 1 in 122, and only 6 and 7 are at distance 3 from 1 in 121; so, if color (1) + 1 is assigned to some node, it is one of them.
In all cases, it is not dificult to see that color (1) + 2 cannot be assigned to any other node (because it is too close either to 1 or to the node labeled with (1) + 1), and hence (1) + 2 is unused. □
For the generality of the choice of (1), we can say that for any two consecutive used colors, the next one must remain unused; in other words, it is possible to use at most two colors out of any three consecutive ones, so (121) ≥ 15 and (122) ≥ 16.
The upper bounds follow by labelings the nodes of 122 with the sequence 0, 3, 6, 9, 12, 15, 1, 4, 7, 10, 13, 16 and the nodes of 121 with the sequence 0, 3, 6, 9, 12, 15, 1, 4, 7, 10, 13. □ Lemma 5. 12 ≤ (2) ≤ 14 when = 7 + with ≥ ≥ 1.
Proof. The lower bound still comes from Lemma 2. The upper bound on derives from the labeling that repeats the sequence 0, 4, 8, 12, 2, 6, 10 for exactly times; for times, between two consecutive 7-long sequences, color 14 is used. It is immediate to check the feasibility of this labeling. □
We conclude this section with the following summarizing theorem, covering all large values of n: Theorem 5. 3Δ = 12 ≤ (2) ≤ 3Δ + 2 = 14 when ≥ 42; moreover (2) = 3Δ = 12 when ≡ 0 mod 7.
It is worth noting that we have got exact results for all the small values of , but we omit them here due to space reasons.
In this section, we propose an (
Consider an embedding of an outerplanar graph = (, ), choose a node , and induce a total order on the nodes by walking clockwise around the external face. Compute a Breadth First Search starting from node so that nodes coming first in the ordering are visited first. As in [6], in the following, such computation will be called Ordered Breadth First Search (OBFS) while Ordered Breadth First Tree (OBFT) is the (unique) tree resulting from this special kind of breadth first search (for an example, see Fig. 2.b). The left-to-right order on each layer of the OBFT induces a numbering of the nodes: we will call , a node of lying on layer of the tree and occupies the -th position in the left-to-right ordering on the layer (see Fig. 2.c).
In [6], an attractive property has been introduced for the OBFT of an outerplanar graph, extending the very well-known one holding for every BFT.
Lemma 6. Let (,ℎ, ′,), ′ ≤ , be a non-tree edge in an OBFT of an outerplanar graph . Then: • either ′ = and (if, w.l.o.g., > ℎ) = ℎ + 1 – see, e.g., edges (4,1, 4,2) and (3,3, 3,4) in Fig. 2.c; • or ′ = − 1 and = + 1, where is the index of the parent of ,ℎ at layer − 1; moreover, ,ℎ is the rightmost child of − 1, (see, e.g., edges (5,2, 4,2) and (3,3, 2,3) in Fig. 2.c). the layer (see Fig. 4(c)).
Before characterizing OBFTs for outerplanar graphs, we have to recall the properties of a general breadth first tree. vl;k; that appear on the outer face of G in this order clockwise for the definition of OBFT. Node vl$1;r can lie either outside or inside this sequence. In the first case a crossing occurs between edges ðvl$1;r; vl;hþ1Þ and v1,1 v3,4
v2,4 v2,5 11
Given an outerplanar graph = (, ) and a palette , a greedy coloring algorithm able to
produce a feasible (
Theorem 6. Algorithm GreedyLabelOuterplanarGraphs correctly (
It is worth noticing that it was not the aim of this author to determine a tight value for but to prove that it is linear in Δ. For this reason, we avoided making the (omitted) proof even more intricate just to decrease the upper bound by a constant number of colors.
In this paper, the (
In particular, the exact (
Discrete Mathematics, 5, pp. 586–595, 1992.
[14] W. K. Hale, Frequency assignment, Theory and application, Proc. IEEE, 68, pp. 1497–1514,
1980,
[15] J. van den Heuvel, R.A. Leese,M.A. Shepherd. Graph labelling and radio channel
assignment. J. Graph Theory, 29, pp. 263–283, 1998.
[16] B.M. Kim, W. Hwang, B.C. Song. (
Combin., 1, pp. 77–85, 2020.
[19] F. S. Roberts, T-colorings of graphs, Discrete Math., 93, pp. 229–245, 1991.
[20] X. Zhang. Some characterization results for the (