Abstract:

Let $f$ be a coloring of the vertices of a connected graph $G$ into colors from the set of colors $\{1, 2, \dots, k\}$. A coloring $f$ on the set of edges of a graph $G$ induces a function $f'(e) = |f(u) - f(v)|$, where $e = uv$ is an arbitrary edge of the graph $G$. The number $f'(e)$ will be called the weight of the edge $e$ induced by the coloring $f$.
        A coloring $f$ is called a graceful $k$-coloring of a graph $G$ if $f'$ is an edge coloring of this graph. We will call a graph an $k$-graceful graph or, simply, a graceful graph if it has a graceful $k$-coloring.
        In general, 4-graceful trees are quite complex. Note that 3-graceful connected graphs have a very simple structure. They are among simple chains of length no more than 3.
        It is easy to establish that any 4-graceful graph does not contain vertices of degree greater than 3. Therefore, we consider trees $T$ whose vertex degrees do not exceed 3. Vertices of degree 3 in a tree $T$ we will call by nodes. We will say that the nodal distance between two nodes $u$ and $v$ of a tree $T$ is equal to $s$ if there is a simple chain from $u$ to $v$ such that the number of internal vertices in it is equal to $s$ and all these internal vertices have degree 2 in the tree $T$. (Of course, the nodal distance is defined not for any pair of nodes.) In this case, we will call a simple chain from $u$ to $v$ an $s$-branch.
        Let us fix some positive integer $s$ and generate a subgraph $T_s$ of the tree $T$ from all nodes and all $s$-branches. The connected components of $T_s$ will be called nodal $s$-components (or simply nodal components) of the tree $T$. 
        The main goal of our work is as follows. 
       1) For all positive integers $s$, find 4-graceful colorings of $s$-branches with given pairs of colors for the initial and final nodes (see Tables 1, 2 and 3).
       2) To consider the properties of 4-graceful colorings of nodal $s$-components for $s\geq 4$ and $s\neq 5$ (see Theorems 1 and 2).
       3) To show how can be found forbidden configurations for 4-graceful trees with using nodal $s$-components (see Theorem 3).