# Adjacent Vertex Distinguishing Total Coloring of Corona Product of
Graphs111Conflict of Interest: Author A declares that she has no conflict of
interest. Author B has received research grants from UNAM - grant PAPIIT-UNAM-
IN117219

Hanna Furmańczyk  Institute of Informatics, Faculty of Mathematics, Physics
and Informatics,
University of Gdańsk, Wita Stwosza 57, 80-309 Gdańsk, Poland
<EMAIL_ADDRESS>Rita Zuazua  Department of Mathematics, Faculty of
Sciences, National Autonomous University of Mexico, Ciudad Universitaria,
Coyoacan, 04510 Mexico, DF, Mexico<EMAIL_ADDRESS>
###### Abstract

An adjacent vertex distinguishing total $k$-coloring $f$ of a graph $G$ is a
proper total $k$-coloring of $G$ such that no pair of adjacent vertices has
the same color sets, where the color set at a vertex $v$, $C^{G}_{f}(v)$, is
$\\{f(v)\\}\cup\\{f(vu)|u\in V(G),vu\in E(G)\\}$. In 2005 Zhang et al. posted
the conjecture (AVDTCC) that every simple graph $G$ has adjacent vertex
distinguishing total $(\Delta(G)+3)$-coloring. In this paper we confirm the
conjecture for many coronas, in particular for generalized, simple and
$l$-coronas of graphs, not relating the results to particular graph classes.

###### keywords:

corona graph , $l$-corona , generalized corona graph , adjacent vertex
distinguishing total coloring , AVDTC Conjecture

###### MSC:

05C15 , 05C76 , 68R10

††journal: Journal of Computational and Applied Mathematics

##  1 Introduction

The processes occurring in the world around us can very often be modeled by
the language of graph theory. The graph coloring problems, vertex, edge as
well as total version, are ones of the best known problems of graph theory.
Proper total coloring was considered for the first time by Rosenfeld in 1970
[16]. In the first decade of this century a new concept appeared in the topic
of graph colorings. Many researchers considered colorings (proper, total or
from lists) such that vertices (all or adjacent) are distinguished either by
sets or multisets or sums. In this paper we investigate the problem of proper
total distinguishing adjacent vertices by sets.

Let $G=(V,E)$ be a simple graph with maximum degree $\Delta(G)$. Let $[k]$
denote the set $\\{1,\ldots,k\\}$ for any positive integer $k$. Suppose that
$f:V\cup E\rightarrow[k]$ is a proper total coloring of $G$, i.e. no two
adjacent edges, no two adjacent vertices, and no edge and its endvertices are
assigned the same color. The smallest number $k$ admitting such a proper total
$k$-coloring is named _total chromatic number_ and is denoted by
$\chi^{\prime\prime}(G)$. Clearly, $\chi^{\prime\prime}(G)\geq\Delta(G)+1$.
Vizing [18], and independly Behzad et al. [1], posted the following
conjecture.

######  Conjecture 1 (TCC, [1, 18]).

For any graph $G$, $\chi^{\prime\prime}(G)\leq\Delta(G)+2.$

For a given proper total $k$-coloring of $G$ and for a vertex $v\in V(G)$, let
$C_{f}(v)$ denote the _color set_ of $v$ with respect to $f$, i.e. the set
$\\{f(v)\\}\cup\\{f(vu)|u\in V(G),vu\in E(G)\\}$. Sometimes we will consider
the color set restricted to some subgraph of $G$. Let $H$ be a subgraph of $G$
and let $v\in V(H)$. Then, $C^{H}_{f}(v)$ denotes the set
$\\{f(v)\\}\cup\\{f(vu)|u\in V(H),vu\in E(H)\\}$. If the total coloring is
clear, we can use the notation of $C(v)$ and $C^{H}(v)$, respectively.

In this paper, we are interested in the smallest number $k$ of colors such
that there is a proper total $k$-coloring of $G$ with the adjacent vertices
being distinguished by their color sets. Such a model was introduced by Zhang
et al. [23] in 2005. More formally, in _adjacent vertex distinguishing total
$k$-coloring_ $f$ (avd total $k$-coloring, for short), we have $C_{f}(u)\neq
C_{f}(v)$ for every pair of vertices $u,v$ such that $uv\in E(G)$. The
smallest $k$ admitting such coloring is called the _adjacent vertex
distinguishing total chromatic number_ (avd total chromatic number, for short)
and is denoted by $\chi_{a}^{\prime\prime}(G)$. Of course,
$\chi_{a}^{\prime\prime}(G)\geq\chi^{\prime\prime}(G)$. It turns out that
there are a lot of examples of graphs for which this inequality is strict,
e.g.
$2l+1=\chi^{\prime\prime}(K_{2l+1})<\chi_{a}^{\prime\prime}(K_{2l+1})=2l+3$
[13].

As a direct consequence of the definition, we have the following relation
between avd total chromatic number and chromatic number, $\chi(G)$, and
chromatic index of a graph $G$, $\chi^{\prime}(G)$.

######  Proposition 1.

For any graph $G$, $\chi^{\prime\prime}_{a}(G)\leq\chi(G)+\chi^{\prime}(G)$.
$\Box$

Taking into account for example Vizing and Brook’s theorems we get

######  Proposition 2.

Let $G\neq K_{n}$ and $G\neq C_{2k+1}$. Then $\chi^{\prime\prime}_{a}(G)\leq
2\Delta(G)+1.$ $\Box$

Huang et al. [12] proved that the bound from the last proposition can be
improved to $2\Delta(G)$. Whereas, for planar graphs Proposition 1 implies

######  Proposition 3.

For any planar graph $G$ we have $\chi^{\prime\prime}_{a}(G)\leq\Delta(G)+5.$
$\Box$

Zhang et al. in [23] determined $\chi_{a}^{\prime\prime}(G)$ for many basic
families of graphs, including cycles, complete graphs, fans, wheels or trees.
Additionally, the following bound on $\chi_{a}^{\prime\prime}(G)$ in terms of
the maximum degree of a graph $\Delta(G)$ was conjectured.

######  Conjecture 2 (AVDTCC, [23]).

For any simple graph $G$, $\chi_{a}^{\prime\prime}(G)\leq\Delta(G)+3$.

The conjecture has been attracting the attention of many graph theorists since
2005. It has been proved for some families of graphs, including planar [2, 6,
10, 11], outerplanar [21], subcubic [3, 13, 20], bipartite [3], and 4-regular
graphs [15]. The last result is proved by giving a relevant algorithm for avd
total 7-coloring of 4-regular graphs. Coker and Johannson [7] used
probabilistic methods to prove that there exists a constant $c$ such that
$\chi^{\prime\prime}_{a}(G)\leq\Delta(G)+c$.

Zhang et al. [23] proved also

######  Lemma 4 ([23]).

If $G$ has two vertices of maximum degree which are adjacent, then
$\chi_{a}^{\prime\prime}(G)\geq\Delta(G)+2$.

######  Lemma 5 ([23]).

If $G$ has $m$ components $G_{i}$, $i\in[m]$, and $|V(G_{i})|\geq 2$,
$i\in[m]$, then
$\chi_{a}^{\prime\prime}(G)=\max\\{\chi_{a}^{\prime\prime}(G_{1}),\chi_{a}^{\prime\prime}(G_{2}),\ldots,\chi_{a}^{\prime\prime}(G_{m})\\}$.

That is why we assume that all graphs considered in this paper are connected.

In this paper we put our attention to graph products. They are interesting and
useful in many situations. The complexity of many problems that deal with very
large and complicated graphs is reduced greatly if one is able to fully
characterize the properties of less complicated prime factors. In the
literature we have some results concerning adjacent vertex distinguishing
total coloring for join graphs of paths with cycles and fans [22, 14], and
some Cartesian products of simple graphs [5, 4, 17, 19]. We consider the
objective problem for corona product of graphs - generalized, simple and
$l$-coronas. They are often close to the boundary between easy and hard
coloring problems [9].

######  Definition 1.

_For a given simple graph $G$ with $V(G)=\\{v_{1},\ldots,v_{n_{G}}\\}$, and
graphs $H_{1},\ldots,$ $H_{n_{G}}$, the_ generalized corona, _denoted by
$G\tilde{\circ}\Lambda_{i=1}^{n_{G}}H_{i}$ or by
$G\tilde{\circ}(H_{1},\ldots,H_{n_{G}})$, is the graph obtained by taking one
copy of graphs $G$, $H_{1},...,H_{n_{G}}$ and joining the $v_{i}$ vertex of
$G$ to every vertex of $H_{i}$ (cf. Fig. 1)._

Figure 1: An example of a generalized corona - graph
$C_{4}\tilde{\circ}(C_{3},P_{3},P_{4},P_{2})$.

In the cases when all graphs $H_{i}$ are isomorphic, i.e. $H_{1}\simeq
H_{2}\simeq\cdots\simeq H_{n_{G}}\simeq H$, the generalized corona is reduced
to _simple_ corona $G\circ H$. Graph $G$ is called the _center graph_ , while
graph $H$ is named the _outer graph_. Such type of graph product was
introduced by Frucht and Harary [8].

Let $v\in V(G)$, by $F_{v}$ we denote the set of edges of $G\circ H$ linking
$v$ with the relevant copy of $H$, and we name it by _fan_ in $v$.

######  Definition 2.

_For any integer $l\geq 2$, the graph $G\circ^{l}H$ is defined as
$G\circ^{l}H=(G\circ^{l-1}H)\circ H$, where $G\circ^{1}H=G\circ H$. Graph
$G\circ^{l}H$ is also named as_ $l$-corona product _of $G$ and $H$. _

In this paper we confirm Conjecture 2 for many coronas, generalized, simple,
or $l$-coronas, of graphs that fulfill the conjecture, not relating the
results to particular graph classes. We conclude the paper with some open
questions.

##  2 Main results

We start with some basic observations.

######  Observation 6.

Let $G$ be a simple graph. If there is avd total $k$-coloring of $G$ then
there is also its avd total $(k+1)$-coloring.

######  Observation 7.

In any avd total $k$-coloring $f$ of a graph $G$, if the degree of a vertex
$u$ is different of the degree of $v$, $u,v\in V(G)$, then $C_{f}(u)\neq
C_{f}(v)$.

Note that every bipartite graph $G$ has $(\Delta(G)+2)$-adjacent-vertex-
distinguishing total coloring such that $\Delta(G)$ colors are used to color
edges of $G$, while the remaining two colors are used to color vertices.
Moreover, we may extend this coloring into adjacent-vertex-distinguishing
total coloring that uses more than $\Delta(G)+2$ colors by introducing new
colors only for vertices.

######  Theorem 8 ([3]).

If $G$ is a bipartite graph, then $\chi^{\prime\prime}_{a}(G)\leq\Delta(G)+2$.

We start our main results from the theorem concerning generalized coronas
$G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}$ where the maximum degree of each graph
$H_{i}$ does not exceed the maximum degree of $G$. It is worth emphasizing
that in the assumption of the theorem we use only avd total coloring of graph
$G$ while graphs $H_{i}$ are colored totally in any proper way.

######  Theorem 9.

Let $G$ and $H_{1},H_{2},\ldots H_{n_{G}}$ be connected simple graphs, each
one on at least two vertices, such that
$\chi^{\prime\prime}_{a}(G)\leq\Delta(G)+t$, $t\geq 2$, and
$\chi^{\prime\prime}(H_{i})\leq\Delta(H_{i})+t_{i}$, $1\leq t_{i}\leq t$, for
each $i\in[n_{G}]$. In addition, let $\Delta(G)\geq\Delta(H_{i})$ for all
$1\leq i\leq n_{G}$. Then,

$\chi_{a}^{\prime\prime}(G\tilde{\circ}\Lambda_{i=1}^{n}H_{i})\leq\Delta(G\tilde{\circ}\Lambda_{i=1}^{n}H_{i})+t.$

###### Proof.

Without loss of generality we can assume that
$\Delta(H_{1})\geq\Delta(H_{2})\geq\cdots\geq\Delta(H_{n_{G}})$. Let
$|V(G)|=n_{G}$ and $|V(H_{i})|=n_{H_{i}}$, $i\in[n_{G}]$. From the assumption,
we have $n_{G}\geq 2$ and $n_{H_{i}}\geq 2$ for every $i\in[n_{G}]$. It is
clear that
$\delta(G)+\min_{i}n_{H_{i}}\leq\Delta(G\tilde{\circ}\Lambda_{i=1}^{n}H_{i})\leq\Delta(G)+\max_{i}n_{H_{i}}$
and the maximum degree of the generalized corona can be realized only by
vertices of $G$.

In order to obtain adjacent vertex distinguishing total
$(\Delta(G\tilde{\circ}\Lambda_{i=1}^{n}H_{i})+t)$-coloring $f$ we start from
any avd total $(\Delta(G)+t)$-coloring of $G$. We will extend the coloring for
all graphs $H_{i}$, $i\in[n_{G}]$, and the relevant fans. We consider
$v_{i}\in V(G)$ with the relevant graph $H_{i}$, for consecutive
$i\in[n_{G}]$. We apply one of the following cases, depending on the relation
between degrees of $G$ and $H_{i}$.

Case 1.

$\Delta(G)>\Delta(H_{i})$ or $\Delta(G)=\Delta(H_{i})$, but $t_{i}<t$.

We color vertices and edges of $H_{i}$ in a proper way with
$\Delta(H_{i})+t_{i}$ colors from the set $[\Delta(H)+t_{i}+1]$, but we do not
use the color assigned to $v_{i}$ in $f|_{G}$. Since
$\Delta(H_{i})+t_{i}<\Delta(G)+t$, it is doable. Finally, we use colors
$\Delta(G)+t+1,\ldots,\Delta(G)+n_{H_{i}}+t$ to color $n_{H_{i}}$ edges in the
fan $F_{v_{i}}$. Note, that these $n_{H_{i}}$ colors are not used in either
$G$ or $H_{i}$.

Case 2.

$\Delta(G)=\Delta(H_{i})$ and $t_{i}=t$.

If we are able to color graph $H_{i}$ with $\Delta(H_{i})+t$ colors in a
proper total way such that color $f(v_{i})$ is not used to color vertices in
$H_{i}$, then we do it. Next, we assign colors
$\Delta(G)+t+1,\ldots,\Delta(G)+n_{H_{i}}+t$ to color $n_{H_{i}}$ edges in the
fan $F_{v_{i}}$. Otherwise, we consider any total $(\Delta(H_{i})+t)$-coloring
of $H_{i}$. Note that taking exactly such a coloring of $H_{i}$ to
$G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}$ results in improper partial total
coloring. The vertices in $H_{i}$ that are assigned color $f(v_{i})$ need to
be recolored into a new color $\Delta(G)+t+1$ and such a modified total
coloring of $H_{i}$ is taken to $G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}$.
Because $n_{H_{i}}\geq 2$ and $H_{i}$ is connected, then we are able to choose
one vertex in $H_{i}$ not colored with $\Delta(G)+t+1$, let us say vertex
$u^{\prime}$, and the edge $v_{i}u^{\prime}$ in the fan $F_{v_{i}}$ can be
assigned color $\Delta(G)+t+1$. The rest of edges in the fan $F_{v_{i}}$ are
colored with $\Delta(G)+t+2,\ldots,\Delta(G)+n_{H}+t$ colors, not used earlier
either in $G$ or in $H_{i}$.

Finally, after coloring all outer graphs and the relevant fans, the total
coloring of the generalized corona is proper. We claim that it is adjacent
vertex distinguishing. In order to justify this we consider the following
cases.

  * 1.

Let $a$ and $b$ be two adjacent vertices in $H_{i}$, i.e. $ab\in E(H_{i})$ for
any $i\in[n_{G}]$. Note that $C^{H_{i}}(a)$, as well as $C^{H_{i}}(b)$, is
completed only by one color in the whole avd total coloring of
$G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}$. In Case 1 the colors used to color
edges in $F_{v_{i}}$ were different from those in $C^{H_{i}}(a)\cup
C^{H_{i}}(b)$ and they have not been used in $H$ before. In Case 2, at least
one of these two vertices $a$ and $b$ is completed by a new color not used
earlier. Thus, $C^{G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}}(a)\neq
C^{G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}}(b)$.

  * 2.

Let $a$ and $b$ be any two adjacent vertices in $G$. We colored them taking
into account only graph $G$, i.e. $C^{G}(a)\neq C^{G}(b)$, next their color
sets were completed by the set of new colors, not used earlier in $G$. Thus,
$C^{G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}}(a)\neq
C^{G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}}(b)$.

  * 3.

Let $a$ be a vertex of $H_{i}$ and let $b$ be a vertex of $G$. Since in the
corona $G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}$, $\deg(a)\leq n_{H_{i}}$ while
$\deg(b)\geq n_{H_{i}}+1$, then $\deg(a)\neq\deg(b)$ and
$C^{G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}}(a)\neq
C^{G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}}(b)$.

∎

As a consequence of the previous theorem, for the case when $H_{i}\simeq
H_{j}$ for any $i,j\in[n_{G}]$, we get the following corollary.

######  Corollary 10.

Let $G$ and $H$ be connected simple graphs on at least two vertices, for which
$\chi_{a}^{\prime\prime}(G)\leq\Delta(G)+t$ with $t\geq 2$ and
$\chi^{\prime\prime}(H)\leq\Delta(H)+t^{\prime}$ with $1\leq t^{\prime}\leq
t$. If $\Delta(G)\geq\Delta(H)$, then

$\chi_{a}^{\prime\prime}(G\circ H)\leq\Delta(G\circ H)+t.$

######  Corollary 11.

Let $G$ and $H$ be connected simple graphs on at least two vertices, for which
$\Delta(G)\geq\Delta(H)$.

  1. 1.

If Conjecture 2 holds for $G$ and Conjecture 1 holds for $H$, then

$\chi_{a}^{\prime\prime}(G\circ H)\leq\Delta(G\circ H)+3.$

  2. 2.

If Conjecture 2 holds for $G$ and $H$, then

$\chi_{a}^{\prime\prime}(G\circ H)\leq\Delta(G\circ H)+3.$

  3. 3.

If $G$ and $H$ are bipartite graphs. Then,

$\chi_{a}^{\prime\prime}(G\circ H)\leq\Delta(G\circ H)+2.$

$\Box$

Observe that $\Delta(G\circ^{l}H)=\Delta(G)+l\cdot n_{H}$, for any $l\geq 1$.
If $\Delta(H)\leq\Delta(G)$ then we immediately have
$\Delta(H)\leq\Delta(G\circ^{l-1}H)$, for any $l\geq 2$. Hence we have the
following generalization of Corollary 10.

######  Corollary 12.

Let $G$ and $H$ be connected simple graphs on at least two vertices, for which
$\Delta(G)\geq\Delta(H)$.

  1. 1.

If Conjecture 2 holds for $G$ and Conjecture 1 holds for $H$, then

$\chi_{a}^{\prime\prime}(G\circ^{l}H)\leq\Delta(G\circ^{l}H)+3,$

for any integer $l\geq 2$.

  2. 2.

If Conjecture 2 holds for $G$ and $H$, then

$\chi_{a}^{\prime\prime}(G\circ^{l}H)\leq\Delta(G\circ^{l}H)+3,$

for any integer $l\geq 2$.

  3. 3.

If $G$ and $H$ are bipartite graphs, then

$\chi_{a}^{\prime\prime}(G\circ^{l}H)\leq\Delta(G\circ^{l}H)+2,$

for any integer $l\geq 2$. $\Box$

One can ask what about the Conjecture 2 for coronas $G\circ H$ where
$\Delta(H)>\Delta(G)$. We also ask how big the difference between maximum
degrees can be to be sure that AVDTC Conjecture holds. We partially answer
these questions.

######  Theorem 13.

Let $G$ and $H$ be connected simple graphs on at least two vertices, for which
Conjecture 2 holds. Let $\Delta(H)=\Delta(G)+1$. Then,

$\chi_{a}^{\prime\prime}(G\circ H)\leq\Delta(G\circ H)+3.$

###### Proof.

If $H$ is a bipartite graph, then, due to Theorem 8, we may start with any avd
total $(\Delta(H)+2)$-coloring of each copy of $H$. In this case we need the
same number of colors for avd total $(\Delta(G)+3)$-coloring of $G$. Hence,
this case can be seen as equivalent to the one given in Case 2 in the proof of
Theorem 10. So, let us assume $H$ is not bipartite. Then an avd total
$(\Delta(G\circ H)+3)$-coloring $f$ of $G\circ H$ can be obtained as follows.

  1. 1.

Color vertices and edges of graph $G$ with $\Delta(G)+3$ colors in adjacent
vertex distinguishing way. We will refer to this part of the coloring as to
$f|_{G}$.

  2. 2.

We will extend our avd total coloring $f|_{G}$ into avd total coloring of each
copy of $H$ in $G\circ H$. Let $v\in V(G)$, $c=f(v)$, and we consider the
relevant copy of $H$. Let $f|_{H}$ denote an avd total
$(\Delta(H)+3)$-coloring of $H$ such that there is a vertex $u\in V(H)$ for
which $f(u)\neq c$ and the color $\Delta(H)+3$ does not belong to color set of
$u$ in $H$, i.e. $\Delta(H)+3\not\in C_{f|_{H}}^{H}(u)$.

Note that such a coloring of $H$ always exists due to the fact that we have at
least two missing colors in a color set of every vertex in $H$. So we color
the chosen $H$, $H\subset G\circ H$, in the desirable way.

Since $\Delta(H)+3=\Delta(G)+4$, the color $\Delta(H)+3$ does not belong to
$C_{f|_{H}}^{H}(u)$, and $\Delta(G)+4$ is not used in $f|_{G}$, we can color
an edge $uv$ in the fan $F_{v}$ with $\Delta(G)+4$.

Note that after this step the partial total coloring $f$ of $G\circ H$ may not
be proper. We need to fix it, if it is the case. We do it in the following
way. If the coloring is improper, i.e. there are vertices in $H$ colored with
$c$, we recolor them to $\Delta(G)+5$. Note that after this recoloring the new
coloring, limited to graph $H$, is certainly proper avd-total-coloring, while
the partial total coloring of the whole corona, received so far, is proper.

  3. 3.

Next, we will complete the coloring of the fan $F_{v}$. If the coloring was
initially not proper, we choose one vertex $w\in V(H)$ such that $w\neq u$ and
$w$ is not colored with $c$. Such a vertex certainly exists, because $H$ is
not bipartite. Note that $vw$ can be colored with $\Delta(G)+5$. We do it. The
rest uncolored $n_{H}-2$ edges in $F_{v}$ are colored with new colors:
$\Delta(G)+6,\ldots,\Delta(G)+n_{H}+3$. Otherwise, we color all uncolored
$n_{H}-1$ edges in $F_{v}$ with $\Delta(G)+5,\ldots,\Delta(G)+n_{H}+3$.

We repeat Step 2 and Step 3 for every $v\in V(G)$ with the relevant copy of
$H$.

Observe that for any vertex $v\in V(G)$, $C^{G\circ
H}(v)=C^{G}(v)\cup\\{\Delta(G)+4,...,\Delta(G)+n_{H}+3\\}$. Since the coloring
$f|_{G}$ was adjacent vertex distinguishing, then also $f$, in accordance to
vertices of $G$, is avd. In addition, for every $uw\in E(H)$, there exists at
least one color $t\in\\{1,2,..,\Delta(G)+3\\}$ such that $t\notin C^{H}(u)\cap
C^{H}(w)$. Hence, the obtained $(\Delta(G\circ H)+3)$-coloring of the whole
corona $G\circ H$ is proper adjacent vertex distinguishing total coloring. ∎

######  Theorem 14.

Let $G$ be a connected simple graph on at least two vertices, for which
Conjecture 2 holds. And let $H$ be the complete graph with order
$n_{H}=\Delta(G)+3$. Then

$\chi_{a}^{\prime\prime}(G\circ H)\leq\Delta(G\circ H)+3.$

###### Proof.

We start from any adjacent vertex distinguishing total
$(\Delta(G)+3)$-coloring of $G$. We will refer to this part of the coloring as
to $f|_{G}$. An extension of $f|_{G}$ into the whole $(\Delta(G\circ
H)+3)$-coloring $f$ of $G\circ H$ is obtained as follows.

Let $v\in V(G)$, $f(v)=c$ with $c\in[\Delta(G)+3]$, which is equivalent to
$c\in[\Delta(H)+1]$. We consider the relevant copy of $H$.

Let $f|_{H}$ be an adjacent vertex distinguishing total
$(\Delta(H)+3)$-coloring of $H$, such that for all $u\in V(H)$,
$f|_{H}(u)\notin\\{c,\Delta(G)+5\\}.$ It is possible because
$H=K_{\Delta(G)+3}$ and we use exactly $\Delta(G)+3$ colors to color vertices.

Observe that for any vertex $u\in V(H)$, $|\overline{C^{H}(u)}|=2,$ and for
any two vertices $u,w$ in $H$, the following holds
$0\leq|\overline{C^{H}(u)}\cap\overline{C^{H}(w)}|\leq 1.$ We claim that there
are two vertices $u,w\in V(H)$ such that
$\overline{C^{H}(u)}\cap\overline{C^{H}(w)}=\emptyset$. Otherwise, consider
two vertices $x_{1},x_{2}\in V(H)$ such that
$\overline{C^{H}(x_{1})}=\\{a,d\\},\overline{C^{H}(x_{2})}=\\{b,d\\}$. Now,
the color $d$ need to belong to a color set of at least one vertex. Let us say
$x_{3}\in V(H)$ is such a vertex that $\overline{C^{H}(x_{3})}=\\{a,b\\}$,
$a\neq d\neq b$, and for any other vertex $x_{4}\in V(H)$ we have only one of
the following possibilities: $\overline{C^{H}(x_{4})}=\\{a,b\\}$, or
$\overline{C^{H}(x_{4})}=\\{a,d\\}$, or $\overline{C^{H}(x_{4})}=\\{d,b\\}$,
which is a contradiction.

Let $\\{u,w\\}\subset V(H)$ such that
$\overline{C^{H}(u)}\cap\overline{C^{H}(w)}=\emptyset$ with
$\overline{C^{H}(u)}=\\{a,b\\},$ $\overline{C^{H}(w)}=\\{d,g\\}$, where
$a,b,d,g$ are four different colors other than $c$. In this case, if it is
necessary, we can recolor the graph $H$ such that
$\overline{C^{H}(u)}=\\{a,\Delta(G)+4\\},\overline{C^{H}(w)}=\\{d,\Delta(G)+5\\}$.
Next we color the edges $f(uv)=\Delta(G)+4$, $f(wv)=\Delta(G)+5$ and we use
the new colors $\\{\Delta(G)+6,\Delta(G)+7,...,\Delta(G)+n_{H}+3\\}$ to the
edges $xv$, where $x\in V(H)\backslash\\{u,w\\}.$

Observe that the obtained total $\Delta(G\circ H)+3)$-coloring of
$\Delta(G\circ H)$ is adjacent vertex distinguishing. Indeed, due to the fact
that $\deg(a)\neq\deg(b)$ for any pair of vertices such that $a\in V(G)$ and
$b\in V(H)$, we need to consider only the case of different color sets for two
adjacent vertices within graph $G$ or $H$. If $a$ and $b$ are two adjacent
vertices in $G$, since $C^{G}(a)\neq C^{G}(b)$ and next their color sets were
completed by the set of new colors not used earlier in $G$, then $C^{G\circ
H}(a)\neq C^{G\circ H}(b)$. On the other hand, if $a$ and $b$ are two adjacent
vertices in $H$, then since their color sets from $f|_{H}$ were completed by
one color and in the case where $u\neq a\neq w$ and $u\neq b\neq w$ it was a
new color not used earlier in $H$, then we get $C^{G\circ H}(a)\neq C^{G\circ
H}(b)$. The only doubt could appear for vertices $u,w$ in $H$, chosen as
above. But since $\overline{C^{H}(u)}\cap\overline{C^{H}(w)}=\emptyset$, then
$\overline{C^{G\circ H)}(u)}\cap[\Delta(G)+5]=a$ and $\overline{C^{G\circ
H)}(w)}\cap[\Delta(G)+5]=d$, $a\neq d$. Thus $C^{G\circ H}(u)\neq C^{G\circ
H}(w)$ and the proof is complete.

∎

######  Proposition 15.

Let $H$ be a connected simple graph with $\Delta(H)\geq 3$ for which
Conjecture 2 holds. Let $\alpha(H)\geq 2$ and let $u_{1}$ and $u_{2}$ be any
two non-adjacent vertices in $H$. Then for any color $c\in[\Delta(H)+1]$ there
is an avd total $(\Delta(H)+3)$-coloring $f$ of $H$ such that all four
conditions hold:

  1. 1.

$\Delta(H)+2\in\overline{C^{H}_{f}(u_{1})}$,

  2. 2.

$\Delta(H)+3\in\overline{C^{H}_{f}(u_{2})}$,

  3. 3.

$f(u_{1})\neq c$,

  4. 4.

$f(u_{2})\neq c$.

###### Proof.

We can easily start from any avd total $(\Delta(H)+3)$-coloring $f$ of $H$
such that $f(u_{1})=c_{1}\neq c$ and $f(u_{2})=c_{2}\neq c$ and
$c_{1},c_{2}\in[\Delta(H)+1]$. It may happen that $c_{1}=c_{2}$.

Now, let us assume that $\overline{C^{H}_{f}(u_{1})}$ does not contain
$\Delta(H)+2$. Since each vertex has at least two missing colors, let us say
$\\{a_{1},a_{2}\\}\subset\overline{C^{H}_{f}(u_{1})}$, then we can exchange
one of missing colors, let us say $a_{1}$, with $\Delta(H)+2$, and vice versa,
in the whole graph $H$. Similarly, if $\overline{C^{H}_{f}(u_{2})}$ does not
contain $\Delta(H)+3$, let
$\\{b_{1},b_{2}\\}\subset\overline{C^{H}_{f}(u_{2})}$. We can choose one of
missing colors, different than $a_{1}$, and exchange it into $\Delta(H)+3$,
and vice versa, also in the whole graph $H$.

Finally, we receive an avd total $(\Delta(H)+3)$-coloring $f$ of $H$
fulfilling the desirable conditions. ∎

######  Theorem 16.

Let $G$ an $H$ be connected simple graphs on at least two vertices, for which
Conjecture 2 holds. Let $\Delta(H)=\Delta(G)+2$ and $\alpha(H)\geq 2$. Then

$\chi_{a}^{\prime\prime}(G\circ H)\leq\Delta(G\circ H)+3.$

###### Proof.

We start from any avd total $(\Delta(G)+3)$-coloring of $G$. We will refer to
this part of the coloring as to $f|_{G}$. Further, we extend this coloring
into the whole corona depending on the form of $H$.

Let $v\in V(G)$ and $f|_{G}(v)=c$, where $c\in[\Delta(G)+3]$, or in other
words $c\in[\Delta(H)+1]$. We consider the relevant copy of $H$. If $H$ is
bipartite, $H=(V_{1}\cup V_{2},E)$, then by Theorem 8,
$\chi_{a}^{\prime\prime}(H)\leq\Delta(H)+2$. By König’s theorem, we color the
edges of $H$ with $\Delta(H)$ colors: color $c$ and $\Delta(H)-1$ other colors
from $[\Delta(H)+1]$. One color among $\\{1,\ldots,\Delta(H)+1\\}$ is not used
to color edges in $H$. We assign it to color all vertices in $V_{1}$, while
$\Delta(G)+4$ is used to color all vertices in $V_{2}$. Next, we choose one
vertex $x\in V_{1}$ and assign $\Delta(G)+4$ to $vx$. Further, we complete the
coloring of edges in the fan $F_{v}$ by coloring the residual uncolored
$n_{H}-1$ edges with different colors from the set
$\\{\Delta(G)+5,\ldots,\Delta(G)+n_{H}+3\\}$. We repeat the procedure for all
copies of $H$. It is easy to see that the coloring $f$ of $G\circ H$ is
adjacent vertex distinguishing total coloring.

Otherwise, i.e. if $H$ is not bipartite, an extension of $f|_{G}$ into the
whole $(\Delta(G\circ H)+3)$-coloring $f$ of $G\circ H$ is obtained as
follows. Let $I$ be any independent vertex set in $H$ of size at least 2 and
let $u_{1},u_{2}$ be any two vertices from $I$.

  1. 1.

Color vertices and edges of $H$ in avd total way with
$\Delta(H)+3=\Delta(G)+5$ colors in such a way that color $\Delta(G)+4$ is
missing in the color set of $u_{1}$, i.e.
$\Delta(G)+4\in\overline{C^{H}(u_{1})}$, and
$\Delta(G)+5\in\overline{C^{H}(u_{2})}$, and $f(u_{1})\neq c$, and
$f(u_{2})\neq c$. This is possible due to Proposition 15.

It may happen that the partial total coloring of $G\circ H$ is improper at
this stage. We will fix it later.

  2. 2.

Assign color $\Delta(G)+4$ to an edge $vu_{1}$ and color $\Delta(G)+5$ to
$vu_{2}$.

  3. 3.

If the partial total coloring of $G\circ H$ is improper then we recolor
vertices colored initially with $c$ into $\Delta(G)+6$.

  4. 4.

Choose any vertex $x\in V\backslash\\{u_{1},u_{2}\\}$ not colored with
$\Delta(G)+6$ and assign $\Delta(G)+6$ to $vx$.

Note that such a vertex always exists because $H$ is not bipartite and there
exists at least one edge with both endvertices in $V\backslash H$. At least
one of them is not colored with $\Delta(G)+6$.

  5. 5.

Complete the coloring of edges in the fan $F_{v}$ by coloring the remaining
uncolored $n_{H}-3$ edges with new colors
$\Delta(G)+7,\ldots,\Delta(G)+n_{H}+3$.

Note, that the only cases for which we really need to check the color sets are
adjacent vertices of $x$ which are colored with $\Delta(G)+6$. But edges in
the fan $F_{v}$ joining such a vertex are colored with completely new colors
not used any more in $F_{v}$ and in the copy of $H$ under consideration. So,
even for such adjacent vertices, their color sets are different. Thus, the
partial coloring of $G\circ H$ is proper and adjacent vertex distinguishing
from the point of view of vertices from the copy of $H$.

We repeat the same procedure for all copies of $H$. Finally, we get an avd
total $\Delta(G\circ H)+3$-coloring of $G\circ H$. The justification for two
adjacent vertices within $G$ is the same as in the proofs of the previous
theorems. The proof is complete. ∎

Up to now, since actually Theorem 14 concerns the case when $\alpha(H)=1$ and
$\Delta(H)=\Delta(G)+2$, we proved Conjecture 2 for all coronas $G\circ H$ of
graphs $G$ and $H$ with $\Delta(H)-\Delta(G)\leq 2$, under some additional
assumptions for $G$ and $H$. Now we present a partial result concerning graphs
with a greater difference, i.e. let $\Delta(H)=\Delta(G)+k$, $k\geq 3$. We
start with $H$ being bipartite and $k=3$.

######  Theorem 17.

Let $G$ be connected simple graphs on at least two vertices, for which
Conjecture 2 holds. Let $H=(V_{1}\cup V_{2},E)$ be a bipartite graph with
$\Delta(H)=\Delta(G)+3$. Then

$\chi_{a}^{\prime\prime}(G\circ H)\leq\Delta(G\circ H)+3.$

###### Proof.

By Theorem 8, $\chi_{a}^{\prime\prime}(H)\leq\Delta(H)+2$. We start from any
$(\Delta(G)+3)$-adjacent-vertex-distinguishing total coloring of $G$. Let
$v\in V(G)$ and $f|_{G}(v)=c$, where $c\in[\Delta(G)+3]$, or in other words
$c\in[\Delta(H)+6]$. We consider the relevant copy of $H$. By König’s theorem,
we color the edges in the relevant copy of $H$ with $\Delta(H)$ colors,
$\Delta(H)=\Delta(G)+3$, among them the color $c$. We assign color
$\Delta(G)+4$ to all vertices in $V_{1}$ while color $\Delta(G)+5$ is assigned
to all vertices from $V_{2}$. Now, let us choose a vertex colored with
$\Delta(G)+4$, let us name it $x_{1}$, $x_{1}\in V_{1}$, and a vertex colored
with $\Delta(G)+5$, let us name it by $x_{2}$, $x_{2}\in V_{2}$. At first, try
to choose non-adjacent vertices or vertices of different degrees. When it is
not possible, choose any two vertices colored appropriately. Let
$f(vx_{1})=\Delta(G)+5$ and let $f(vx_{2})=\Delta(G)+4$. If $C^{G\circ
H}(x_{1})=C^{G\circ H}(x_{2})$, then recolor $x_{2}$ into $\Delta(G)+6$ and
choose any vertex in the same partition, let us say $x_{3}$, $x_{3}\in V_{2}$,
and color $vx_{3}$ with $\Delta(G)+6$, otherwise we assign $\Delta(G)+6$ to
any uncolored edge in the $F_{v}$. Next, we complete the coloring of edges in
the fan $F_{v}$ by coloring the remaining uncolored $n_{H}-3$ edges with new
colors $\Delta(G)+7,\ldots,\Delta(G)+n_{H}+3$. Note that the partial coloring
of $G\circ H$ is proper and adjacent vertex distinguishing from the point of
view of vertices from the copy of $H$.

We repeat the same procedure for all vertices $v\in V(G)$ and the relevant
copies of $H$.

Since we completed $C^{G}_{f}(v)$, for each $v\in V(G)$, by the same set of
colors $\\{\Delta(G)+4,\ldots,\Delta(G)+n_{H}+3\\}$, and taking into account
the previous reasoning for color sets of any two adjacent vertices from $H$,
the total coloring of the whole corona is adjacent vertex distinguishing. The
proof is complete. ∎

Note that a similar idea applied to $H$ being bipartite graph, in particular
complete bipartite graph, with $\Delta(H)=\Delta(G)+k$ for $k\geq 4$ will not
work. We mean assigning only $\Delta(H)$ colors to edges of $H$ and assigning
colors $\Delta(G)+4,\ldots,\Delta(G)+n_{H}+3$ to edges of a fan $F_{v}$. Since
in such solutions all $\Delta(H)$ colors used to color edges of $H$ are
present in color sets of all vertices in $H$, then we can use none of these
colors to color edges in $F_{v}$ and thus such an approach would involve more
than $\Delta(G\circ H)+3$ colors, for $k\geq 4$. Hence, we certainly need to
color edges of $H$ with more colors than only $\Delta(H)$.

Now, let us consider more general graphs. We take an attempt of generalization
of the method given in the proof of Theorem 16. The basis of this method is
such an avd total $(\Delta(H)+3)$-coloring $f|_{H}$ of $H$ that there is a set
of non-adjacent vertices $U=\\{u_{1},\ldots,u_{k}\\}$ for which the colors
from $[\Delta(H)+3]\backslash[\Delta(G)+3]$ are missing colors for vertices in
$U$. For $k=2$ such a coloring was easy to achieve and it was guaranteed by
Proposition 15. For a greater $k$ we need additional conditions for degrees of
$u\in U$.

######  Proposition 18.

Let $H$ be a connected simple graph with $\Delta(H)\geq k+1$ for which
Conjecture 2 holds. Let $\alpha(H)\geq k$ and let $u_{1},\ldots,u_{k}$ be any
$k$ non-adjacent vertices in $H$ such that $\deg(u_{1})\leq\Delta(H)$,
$\deg(u_{2})\leq\Delta(H)$, $\deg(u_{i})\leq\Delta(H)-i+2$ for
$i\in\\{3,\ldots,k-2\\}$. Then for any color $c\in[\Delta(H)-k+4]$ there is an
avd total $(\Delta(H)+3)$-coloring $f$ of $H$ such that all the following
conditions hold:

  1. 1.

$\Delta(H)+1+i\in\overline{C^{H}_{f}(u_{i})}$, $i\in[k]$,

  2. 2.

$f(u_{i})\neq c$, $i\in[k]$.

We remain the full proof for the reader, but it is easy to see that the
conditions for degrees of chosen vertices in an independent set of size at
least $k$ guarantee us that
$|\bigcup_{i\in[k]}\overline{C^{H}_{f}(u_{i})}|\geq k$. So we are able to
exchange colors in $H$ to achieve the desirable conditions. Of course, the
conditions for degrees in Proposition 18 are not the only one guaranteeing us
”good” avd total coloring of $H$.

######  Theorem 19.

Let $G$ an $H$ be connected simple graphs on at least two vertices, for which
Conjecture 2 holds. Let $k\geq 3$ be an integer, $\Delta(H)=\Delta(G)+k$, and
$\alpha(H)\geq k$. If there exist $k$ non-adjacent vertices in $H$
$u_{1},\ldots,u_{k}$ such that $\deg(u_{1})\leq\Delta(H)$,
$\deg(u_{2})\leq\Delta(H)$, $\deg(u_{i})\leq\Delta(H)-i+2$ for
$i\in\\{3,\ldots,k-2\\}$ then

$\chi_{a}^{\prime\prime}(G\circ H)\leq\Delta(G\circ H)+3.$

###### Proof.

We start from any adjacent vertex distinguishing total
$(\Delta(G)+3)$-coloring of $G$. We will refer to this part of the coloring as
to $f|_{G}$. An extension of $f|_{G}$ into the whole $(\Delta(G\circ
H)+3)$-coloring $f$ of $G\circ H$ is obtained as follows. Let
$u_{1},\ldots,u_{k}$ be any $k$ non-adjacent vertices fulfilling the
assumption of the theorem.

  1. 1.

Color vertices and edges of $H$ in avd total way with
$\Delta(H)+3=\Delta(G)+k+3$ colors in such a way that color $\Delta(G)+3+i$ is
missing in the color set of $u_{i}$, i.e.
$\Delta(G)+3+i\in\overline{C^{H}(u_{i})}$, $i\in[k]$, and none of vertices
$u_{i},\ldots,u_{k}$ is colored with $c$. This is possible due to Proposition
18.

It may happen that the partial total coloring of $G\circ H$ is improper at
this stage. We will fix it later.

  2. 2.

Assign color $\Delta(G)+3+i$ to an edge $vu_{i}$, for every $i\in[k]$.

  3. 3.

If the partial total coloring of $G\circ H$ is improper then we recolor
vertices colored initially with $c$ into $\Delta(G)+k+4$.

  4. 4.

Choose any vertex $x\in V\backslash\\{u_{1},\ldots,u_{k}\\}$ not colored with
$\Delta(G)+k+4$ and assign $\Delta(G)+k+4$ to $vx$. Note that such a vertex
always exists. Since $\Delta(H)\geq k+1$ there must exist an edge whose
endvertices are out of the set $\\{u_{1},\ldots,u_{k}\\}$, then at least one
of the endvertices of such an edge is not colored with $\Delta(G)+k+4$.

  5. 5.

Complete the coloring of edges in the fan $F_{v}$ by coloring the remaining
uncolored $n_{H}-k-1$ edges with new colors
$\Delta(G)+k+5,\ldots,\Delta(G)+n_{H}+3$. Note, that the only cases for which
we really need to check the color sets are adjacent vertices of $x$ which are
colored with $\Delta(G)+k+4$. But edges in the fan $F_{v}$ joining such
vertices are colored with completely new colors not used any more in $F_{v}$
and in the copy of $H$ under consideration. So, even for such adjacent
vertices, their color sets are different. Thus, the partial coloring of
$G\circ H$ is proper and adjacent vertex distinguishing from the point of view
of vertices from the copy of $H$.

We repeat the same procedure for all copies of $H$. Finally, we get a total
$(\Delta(G\circ H)+3)$-coloring of $G\circ H$. Since we completed
$C^{G}_{f}(v)$, for each $v\in V(G)$, by the same set of colors
$\\{\Delta(G)+4,\ldots,\Delta(G)+n_{H}+3\\}$, the total coloring of the whole
corona is adjacent vertex distinguishing. The proof is complete. ∎

##  3 Conclusion

In the paper we considered adjacent vertex distinguishing total coloring of
corona graphs in the context of AVDTC Conjecture posted by Zhang in 2005. We
confirmed this conjecture for:

  * 1.

generalized coronas $G\tilde{\circ}\Lambda_{i=1}^{n}H_{i}$ with
$\Delta(G)\geq\Delta(H_{i})$, under the assumption that Conjecture 2 holds for
$G$ and Conjecture 1 holds for every $H_{i}$, $i\in[n_{G}]$;

  * 2.

all simple coronas $G\circ H$ with $\Delta(H)-\Delta(G)\leq 2$, under the
assumption that Conjecture 2 holds for $G$ and $H$;

Actually, the assumption for graph $H$ can be a little weaker. Our proofs show
that it is enough that Conjecture 1 holds for $H$.

  * 3.

all simple coronas $G\circ H$ with $\Delta(H)=\Delta(G)+3$, where $H$ is
bipartite and Conjecture 2 holds for $G$;

  * 4.

some simple coronas $G\circ H$ with $\Delta(H)=\Delta(G)+k$, $k\geq 3$ under
some additional constraints - for details see Theorem 19.

Taking into account the results known from the literature and taking the
results from this work, we can replace our general graphs $G$ and $H$ with
particular graph classes fulfilling Conjecture 1 and 2. In Table 1 we present
only exemplary results.

$G$ $H$ | path | cycle | 3-regular | 4-regular
---|---|---|---|---
path | ✓ | ✓ | ✓ | ✓
cycle | ✓ | ✓ | ✓ | ✓
3-regular | ✓ | ✓ | ✓ | ✓
4-regular | ✓ | ✓ | ✓ | ✓
complete graph $K_{n}$, $n\geq 6$ | ✓ | ✓ | ✓ | ✓
Table 1: An exemplary graph classes of $G$ and $H$ such that Conjecture 2
holds for $G\circ H$.

One can ask what about the remaining coronas not covered by the results of
this paper. We retain this for a further investigation and as an open problem
for other graph theorists.

Compliance with Ethical Standards:

Funding: This study was funded by UNAM (Grant PAPIIT-UNAM-IN117219) - Author
B.

Ethical approval: This article does not contain any studies with human
participants or animals performed by any of the authors.

Statements and Declarations: The manuscript has no associated data.

## References

  * Behzad et al. [1967] Behzad, M., Chartrand, G., Jr, J.C., 1967.  The colour numbers of complete graphs.  J. Lond. Math. Soc. 42, 226–228.
  * Chang et al. [2020] Chang, Y., Hu, J., Wang, G., Yu, X., 2020.  Adjacent vertex distinguishing total coloring of planar graphs with maximum degree $8$.  Discrete Math. 343, 112014\.
  * Chen [2008] Chen, X., 2008.  On the adjacent vertex distinguishing total coloring numbers of graphs with $\delta=3$.  Discrete Math. 308.
  * Chen and Zhang [2006] Chen, X., Zhang, Z., 2006.  Adjacent-vertex-distinguishing total chromatic number of $p_{m}\times k_{n}$.  J. Math. Research & Exposition 26, 489–494.
  * Chen et al. [2008] Chen, X., Zhang, Z., Sang, Y., 2008.  A note on adjacent-vertex-distinguishing total chromatic numbers for $p_{m}\times p_{n}$, $p_{m}\times c_{n}$ and $c_{m}\times c_{n}$.  J. Math. Research & Exposition 28, 789–798.
  * Cheng et al. [2016] Cheng, X., Wang, G., Wu, J., 2016.  The adjacent vertex distinguishing total chromatic numbers of planar graphs with $\delta=10$.  J. Comb. Optim. , 1–15.
  * Coker and Johannson [2012] Coker, T., Johannson, K., 2012\.  The adjacent vertex distinguishing total chromatic number.  Discrete Math. 312, 2741–2750.
  * Frucht and Harary [1970] Frucht, R., Harary, F., 1970\.  On the corona of two graphs.  Aequationes Math. 4, 322–325.
  * Furmańczyk and Kubale [2016] Furmańczyk, H., Kubale, M., 2016\.  Equitable coloring of corona products of cubic graphs is harder than ordinary coloring.  Ars Mathematica Contemporanea 10, 333–347.
  * Hu et al. [2019] Hu, J., Wang, G., Wu, J., Yang, D., Yu, X., 2019.  Adjacent vertex distinguishing total coloring of planar graphs with maximum degree 9.  Discrete Math. 342, 1392–1402.
  * Huang and Wang [2012] Huang, D., Wang, W., 2012.  Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree.  Sci. Sin. Math. 42, 151–164.
  * Huang et al. [2012] Huang, D., Wang, W., Yan, C., 2012.  A note on the adjacent vertex distinguishing total chromatic number of graphs.  Discrete Math. 312, 3544–3546.
  * Hulgan [2009] Hulgan, J., 2009.  Concise proofs for adjacent vertex-distinguishing total colorings.  Discrete Math. 309, 2548–2550.
  * Li et al. [2006] Li, J., Zhang, Z., Wang, Z., Wei, B., Yan, L., 2006\.  On the adjacent vertex-distinguishing equitable-total chromatic number of $p_{m}\lor f_{n}$.  International Journal of Pure and Applied Mathematics 29, 159–169.
  * Papaioannou and Raftopoulou [2014] Papaioannou, A., Raftopoulou, C., 2014\.  On the avdtc of 4-regular graphs.  Discrete Math. 330, 20–40.
  * Rosenfeld [1970] Rosenfeld, M., 1970.  On the total coloring of certain graphs.  Israel J. Math. 9, 396–402.
  * Sun and Sun [2007] Sun, Y., Sun, L., 2007.  The (adjacent) vertex-distinguishing total coloring of the mycielski graphs and the cartesian product graphs, in: Discrete Geometry, Combinatorics and Graph Theory, Springer. pp. 200–205.
  * Vizing [1964] Vizing, V.G., 1964.  On an estimate of the chromatic class of a p-graph.  Metody Diskret. Analiz. , 25–30.
  * Wang [2017] Wang, G., 2017.  Relation between cartesian product and adjacent vertex distinguishing coloring.  J. Zhejiang University 44, 520–525.
  * Wang [2007] Wang, H., 2007.  On the adjacent vertex-distinguishing total chromatic numbers of the graphs with $\delta(g)=3$.  J. Comb. Optimization 14, 87–109.
  * Wang and Wang [2010] Wang, Y., Wang, W., 2010.  Adjacent vertex distinguishing total colorings of outerplanar graphs.  J. Comb. Optimization 19, 123–133.
  * Wang et al. [2007] Wang, Z., Yan, L., Zhang, Z., 2007.  Vertex distinguishing equitable total chromatic number of join graph.  Acta Mathematicae Applicatae Sinica, English Series 23, 433–438.
  * Zhang et al. [2005] Zhang, Z., Chen, X., Li, J., Yao, B., Lu, X., Wang, J., 2005.  On the adjacent vertex distinguishing total coloring of graphs.  Sci. China Ser. A 48, 289–299.


$\text{GFP}_{D_{3},D_{3},-2}(23)$ and its image in
$\text{GFP}_{D_{3},D_{3},4}(28)$

Figure 16. The bijections $\phi_{2,23}^{(0)}$, $\phi_{1,23}^{(1)}$ and
$\phi_{1,23}^{(2)}$.

In general not much is known about the functions
$f_{D_{k},D_{k},k^{\prime}}(q)$ for arbitrary $k$ and $k^{\prime}$. As
mentioned earlier the functions $\Phi_{k}(q)(=f_{D_{k},D_{k},0}(q))$ are
studied in Andrews' book [1], and we saw that $\Phi_{1}(q)$ and $\Phi_{2}(q)$
have product expansions (which gave us product expansions for the specialised
normalizing factors). It turns out that $\Phi_{3}(q)$ also has a product
expansion (proved in Corollary $5.1$ of [1], assuming Jacobi triple product)
and so $S_{0}^{(3)}(q)$ can be written as:

$\displaystyle S_{0}^{(3)}(q)=\Phi_{3}(q)$
$\displaystyle=1+q+3q^{2}+6q^{3}+11q^{4}+18q^{5}+31q^{6}+49q^{7}+78q^{8}+...$
$\displaystyle=\prod_{i\geq
1}\frac{(1-q^{12i-6})}{(1-q^{6i-5})(1-q^{6i-4})^{2}(1-q^{6i-3})^{3}(1-q^{6i-2})^{2}(1-q^{6i-1})(1-q^{12i})}$

As in the $2$-exclusion case it would be interesting to know if this could be
proved using purely probabilistic methods. It would also be interesting to
know whether the other functions $f_{D_{3},D_{3},-1}(q)$ and
$f_{D_{3},D_{3},-2}(q)$ are products, as this would imply that the normalising
factors $S_{-1}^{(3)}(q)$ and $S_{-2}^{(3)}(q)$ are products.

For $k\geq 4$ the functions $\Phi_{k}(q)$ are not expected to be products, but
can be shown to be sums of products. However the formulae are very tedious to
write down and probably not too illuminating.

We finish with another natural question. We have seen that the family of (non-
degenerate) nearest neighbour interacting $0$-$1$-$2$ systems on $\mathbb{Z}$
satisfying the blocking measure axioms can be stood up in a uniform way,
leading to three variable Jacobi style identities. By specialising to the case
of $2$-exclusion we then get two variable identities that are a special case
of Theorem 5.6 (setting $k=2$). Is there a family of $0$-$1$-…-$k$ processes
for each $k$ that is nicely behaved (i.e. has blocking measure and can be
uniformly stood up) giving a multivariable identity that explains all cases of
Theorem 5.6? In general we cannot expect the whole family of $0$-$1$…-$k$
systems on $\mathbb{Z}$ to be this well behaved (the stood up processes no
longer have nearest neighbour interactions). However, there could be a low
dimensional subfamily of processes for each $k$ that works.

## Appendix

The following are the non-empty sets $\text{GFP}_{D_{2},D_{2},0,m}(n)$ for
$0\leq n\leq 8$, whose sizes agree with the coefficients in the expansion of
$S_{\text{even}}(\tilde{q},t)$ given in Section $3.3$.

$\text{GFP}_{D_{2},D_{2},0,0}(0)=\left\\{\binom{-}{-}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,2}(1)=\left\\{\binom{0}{0}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,0}(2)=\left\\{\binom{0\,0}{0\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,2}(2)=\left\\{\binom{1}{0},\binom{0}{1}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,2}(3)=\left\\{\binom{2}{0},\binom{1}{1},\binom{0}{2},\binom{1\,0}{0\,0},\binom{0\,0}{1\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,0}(4)=\left\\{\binom{1\,1}{0\,0},\binom{0\,0}{1\,1}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,2}(4)=\left\\{\binom{3}{0},\binom{2}{1},\binom{1}{2},\binom{0}{3},\binom{2\,0}{0\,0},\binom{0\,0}{2\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,4}(4)=\left\\{\binom{1\,0}{1\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,2}(5)=\left\\{\binom{4}{0},\binom{3}{1},\binom{2}{2},\binom{1}{3},\binom{0}{4},\binom{3\,0}{0\,0},\binom{2\,1}{0\,0},\binom{1\,1}{1\,0},\binom{1\,0}{1\,1},\binom{0\,0}{2\,1},\binom{0\,0}{3\,0},\binom{1\,0\,0}{1\,0\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,4}(5)=\left\\{\binom{2\,0}{1\,0},\binom{1\,0}{2\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,0}(6)=\left\\{\binom{2\,2}{0\,0},\binom{1\,1}{1\,1},\binom{0\,0}{2\,2}\right\\},$
$\displaystyle\text{GFP}_{D_{2},D_{2},0,2}(6)=\bigg{\\{}$
$\displaystyle\binom{5}{0},\binom{4}{1},\binom{3}{2},\binom{2}{3},\binom{1}{4},\binom{0}{5},\binom{4\,0}{0\,0},\binom{3\,1}{0\,0},\binom{2\,0}{1\,1},$
$\displaystyle\binom{1\,1}{2\,0},\binom{0\,0}{3\,1},\binom{0\,0}{4\,0},\binom{2\,0\,0}{1\,0\,0},\binom{1\,1\,0}{1\,0\,0},\binom{1\,0\,0}{1\,1\,0},\binom{1\,0\,0}{2\,0\,0}\bigg{\\}},$
$\text{GFP}_{D_{2},D_{2},0,4}(6)=\left\\{\binom{3\,0}{1\,0},\binom{2\,1}{1\,0},\binom{2\,0}{2\,0},\binom{1\,0}{2\,1},\binom{1\,0}{3\,0}\right\\},$
$\displaystyle\text{GFP}_{D_{2},D_{2},0,2}(7)=\bigg{\\{}$
$\displaystyle\binom{6}{0},\binom{5}{1},\binom{4}{2},\binom{3}{3},\binom{2}{4},\binom{1}{5},\binom{0}{6},\binom{5\,0}{0\,0},\binom{4\,1}{0\,0},\binom{3\,2}{0\,0},$
$\displaystyle\binom{2\,2}{1\,0},\binom{3\,0}{1\,1},\binom{2\,1}{1\,1},\binom{1\,1}{2\,1},\binom{1\,1}{3\,0},\binom{1\,0}{2\,2},\binom{0\,0}{3\,2},\binom{0\,0}{4\,1},$
$\displaystyle\binom{0\,0}{5\,0},\binom{3\,0\,0}{1\,0\,0},\binom{2\,0\,0}{2\,0\,0},\binom{2\,0\,0}{1\,1\,0},\binom{1\,1\,0}{2\,0\,0},\binom{1\,1\,0}{1\,1\,0},\binom{1\,0\,0}{3\,0\,0}\bigg{\\}},$
$\text{GFP}_{D_{2},D_{2},0,4}(7)=\left\\{\binom{4\,0}{1\,0},\binom{3\,1}{1\,0},\binom{3\,0}{2\,0},\binom{2\,1}{2\,0},\binom{2\,0}{2\,1},\binom{2\,0}{3\,0},\binom{1\,0}{3\,1},\binom{1\,0}{4\,0},\binom{2\,1\,0}{1\,0\,0},\binom{1\,0\,0}{2\,1\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},0,0}(8)=\left\\{\binom{3\,3}{0\,0},\binom{2\,2}{1\,1},\binom{1\,1}{2\,2},\binom{0\,0}{3\,3},\binom{1\,1\,0\,0}{1\,1\,0\,0}\right\\},$
$\displaystyle\text{GFP}_{D_{2},D_{2},0,2}(8)=\bigg{\\{}$
$\displaystyle\binom{7}{0},\binom{6}{1},\binom{5}{2},\binom{4}{3},\binom{3}{4},\binom{2}{5},\binom{1}{6},\binom{0}{7},\binom{6\,0}{0\,0},\binom{5\,1}{0\,0},\binom{4\,2}{0\,0},\binom{4\,0}{1\,1},$
$\displaystyle\binom{3\,1}{1\,1},\binom{2\,2}{2\,0},\binom{2\,0}{2\,2},\binom{1\,1}{3\,1},\binom{1\,1}{4\,0},\binom{0\,0}{4\,2},\binom{0\,0}{5\,1},\binom{0\,0}{6\,0},\binom{1\,0\,0}{4\,0\,0},\binom{2\,2\,0}{1\,0\,0},$
$\displaystyle\binom{2\,1\,1}{1\,0\,0},\binom{1\,0\,0}{2\,1\,1},\binom{3\,0\,0}{2\,0\,0},\binom{2\,0\,0}{3\,0\,0},\binom{3\,0\,0}{1\,1\,0},\binom{1\,1\,0}{3\,0\,0},\binom{1\,0\,0}{2\,2\,0},\binom{4\,0\,0}{1\,0\,0}\bigg{\\}},$
$\displaystyle\text{GFP}_{D_{2},D_{2},0,4}(8)=\bigg{\\{}$
$\displaystyle\binom{5\,0}{1\,0},\binom{4\,1}{1\,0},\binom{3\,2}{1\,0},\binom{4\,0}{2\,0},\binom{3\,1}{2\,0},\binom{3\,0}{3\,0},\binom{2\,1}{3\,0},\binom{2\,1}{2\,1},\binom{3\,0}{2\,1}\binom{2\,0}{3\,1},\binom{2\,0}{4\,0},$
$\displaystyle\binom{1\,0}{3\,2},\binom{1\,0}{4\,1},\binom{1\,0}{5\,0},\binom{3\,1\,0}{1\,0\,0},\binom{2\,1\,0}{2\,0\,0},\binom{2\,1\,0}{1\,1\,0},\binom{1\,1\,0}{2\,1\,0},\binom{2\,0\,0}{2\,1\,0},\binom{1\,0\,0}{3\,1\,0}\bigg{\\}}.$

The following are the non-empty sets $\text{GFP}_{D_{2},D_{2},-1,m}(n)$ for
$0\leq n\leq 8$, whose sizes agree with the coefficients in the expansion of
$S_{\text{odd}}(\tilde{q},t)$ given in Section $3.3$.

$\text{GFP}_{D_{2},D_{2},-1,1}(0)=\left\\{\binom{-}{0}\right\\},$
$\text{GFP}_{D_{2},D_{2},-1,1}(1)=\left\\{\binom{-}{1},\binom{-\,0}{0\,\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},-1,1}(2)=\left\\{\binom{-}{2},\binom{-\,1}{0\,\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},-1,3}(2)=\left\\{\binom{-\,0}{1\,\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},-1,1}(3)=\left\\{\binom{-}{3},\binom{-\,2}{0\,\,0},\binom{-\,0}{1\,\,1},\binom{-\,0\,0}{1\,\,0\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},-1,3}(3)=\left\\{\binom{-\,1}{1\,\,0},\binom{-\,0}{2\,\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},-1,1}(4)=\left\\{\binom{-}{4},\binom{-\,3}{0\,\,0},\binom{-\,1}{1\,\,1},\binom{-\,0\,0}{2\,\,0\,0},\binom{-\,0\,0}{1\,\,1\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},-1,3}(4)=\left\\{\binom{-\,2}{1\,\,0},\binom{-\,1}{2\,\,0},\binom{-\,0}{2\,\,1},\binom{-\,0}{3\,\,0},\binom{-\,1\,0}{1\,\,0\,0}\right\\},$
$\text{GFP}_{D_{2},D_{2},-1,1}(5)=\left\\{\binom{-}{5},\binom{-\,4}{0\,\,0},\binom{-\,2}{1\,\,1},\binom{-\,0}{2\,\,2},\binom{-\,1\,1}{1\,\,0\,0},\binom{-\,0\,0}{3\,\,0\,0}\right\\},$
$\displaystyle\text{GFP}_{D_{2},D_{2},-1,3}(5)=\bigg{\\{}$
$\displaystyle\binom{-\,3}{1\,\,0},\binom{-\,2}{2\,\,0},\binom{-\,1}{2\,\,1},\binom{-\,1}{3\,\,0},\binom{-\,0}{3\,\,1},\binom{-\,0}{4\,\,0},$
$\displaystyle\binom{-\,2\,0}{1\,\,0\,0},\binom{-\,1\,0}{1\,\,1\,0},\binom{-\,1\,0}{2\,\,0\,0},\binom{-\,0\,0}{2\,\,1\,0}\bigg{\\}},$
$\displaystyle\text{GFP}_{D_{2},D_{2},-1,1}(6)=\bigg{\\{}$
$\displaystyle\binom{-}{6},\binom{-\,5}{0\,\,0},\binom{-\,3}{1\,\,1},\binom{-\,1}{2\,\,2},\binom{-\,1\,1}{1\,\,1\,0},\binom{-\,1\,1}{2\,\,0\,0},$
$\displaystyle\binom{-\,0\,0}{2\,\,1\,1},\binom{-\,0\,0}{2\,\,2\,0},\binom{-\,0\,0}{4\,\,0\,0},\binom{-\,1\,0\,0}{1\,\,1\,0\,0}\bigg{\\}},$
$\displaystyle\text{GFP}_{D_{2},D_{2},-1,3}(6)=\bigg{\\{}$
$\displaystyle\binom{-\,4}{1\,\,0},\binom{-\,3}{2\,\,0},\binom{-\,2}{2\,\,1},\binom{-\,2}{3\,\,0},\binom{-\,1}{3\,\,1},\binom{-\,1}{4\,\,0},\binom{-\,0}{3\,\,2},\binom{-\,0}{4\,\,1},$
$\displaystyle\binom{-\,0}{5\,\,0},\binom{-\,3\,0}{1\,\,0\,0},\binom{-\,2\,1}{1\,\,0\,0},\binom{-\,2\,0}{1\,\,1\,0},\binom{-\,2\,0}{2\,\,0\,0},\binom{-\,1\,0}{3\,\,0\,0},\binom{-\,0\,0}{3\,\,1\,0}\bigg{\\}},$
$\text{GFP}_{D_{2},D_{2},-1,5}(6)=\left\\{\binom{-\,1\,0}{2\,\,1\,0}\right\\},$
$\displaystyle\text{GFP}_{D_{2},D_{2},-1,1}(7)=\bigg{\\{}$
$\displaystyle\binom{-}{7},\binom{-\,6}{0\,\,0},\binom{-\,4}{1\,\,1},\binom{-\,2}{2\,\,2},\binom{-\,0}{3\,\,3},\binom{-\,2\,2}{1\,\,0\,0},\binom{-\,1\,1}{3\,\,0\,0},$
$\displaystyle\binom{-\,0\,0}{2\,\,2\,1},\binom{-\,0\,0}{3\,\,1\,1},\binom{-\,0\,0}{5\,\,0\,0},\binom{-\,2\,0\,0}{1\,\,1\,0\,0},\binom{-\,1\,1\,0}{1\,\,1\,0\,0}\bigg{\\}},$
$\displaystyle\text{GFP}_{D_{2},D_{2},-1,3}(7)=\bigg{\\{}$
$\displaystyle\binom{-\,5}{1\,\,0},\binom{-\,4}{2\,\,0},\binom{-\,3}{2\,\,1},\binom{-\,3}{3\,\,0},\binom{-\,2}{3\,\,1},\binom{-\,2}{4\,\,0},\binom{-\,1}{3\,\,2},\binom{-\,1}{4\,\,1},\binom{-\,1}{5\,\,0},\binom{-\,0}{4\,\,2},$
$\displaystyle\binom{-\,0}{5\,\,1},\binom{-\,0}{6\,\,0},\binom{-\,4\,0}{1\,\,0\,0},\binom{-\,3\,1}{1\,\,0\,0},\binom{-\,3\,0}{1\,\,1\,0},\binom{-\,3\,0}{2\,\,0\,0},\binom{-\,2\,1}{1\,\,1\,0},\binom{-\,2\,1}{2\,\,0\,0},$
$\displaystyle\binom{-\,2\,0}{3\,\,0\,0},\binom{-\,1\,1}{2\,\,1\,0},\binom{-\,1\,0}{2\,\,1\,1},\binom{-\,1\,0}{2\,\,2\,0},\binom{-\,1\,0}{4\,\,0\,0},\binom{-\,0\,0}{3\,\,2\,0},\binom{-\,0\,0}{4\,\,1\,0},\binom{-\,1\,0\,0}{2\,\,1\,0\,0}\bigg{\\}},$
$\text{GFP}_{D_{2},D_{2},-1,5}(7)=\left\\{\binom{-\,1\,0}{3\,\,1\,0},\binom{-\,2\,0}{2\,\,1\,0},\right\\},$
$\displaystyle\text{GFP}_{D_{2},D_{2},-1,1}(8)=\bigg{\\{}$
$\displaystyle\binom{-}{8},\binom{-\,7}{0\,\,0},\binom{-\,5}{1\,\,1},\binom{-\,3}{2\,\,2},\binom{-\,1}{3\,\,3},\binom{-\,2\,2}{1\,\,1\,0},\binom{-\,2\,2}{2\,\,0\,0},\binom{-\,1\,1}{2\,\,1\,1},$
$\displaystyle\binom{-\,1\,1}{2\,\,2\,0},\binom{-\,1\,1}{4\,\,0\,0},\binom{-\,0\,0}{3\,\,3\,0},\binom{-\,0\,0}{4\,\,1\,1},\binom{-\,0\,0}{6\,\,0\,0},\binom{-\,3\,0\,0}{1\,\,1\,0\,0},\binom{-\,1\,0\,0}{2\,\,2\,0\,0}\bigg{\\}},$
$\displaystyle\text{GFP}_{D_{2},D_{2},-1,3}(8)=\bigg{\\{}$
$\displaystyle\binom{-\,6}{1\,\,0},\binom{-\,5}{2\,\,0},\binom{-\,4}{2\,\,1},\binom{-\,4}{3\,\,0},\binom{-\,3}{3\,\,1},\binom{-\,3}{4\,\,0},\binom{-\,2}{3\,\,2},\binom{-\,2}{4\,\,1},\binom{-\,2}{5\,\,0}\binom{-\,1}{4\,\,2},$
$\displaystyle\binom{-\,1}{5\,\,1},\binom{-\,1}{6\,\,0},\binom{-\,0}{4\,\,3},\binom{-\,0}{5\,\,2},\binom{-\,0}{6\,\,1},\binom{-\,0}{7\,\,0},\binom{-\,5\,0}{1\,0\,0},\binom{-\,4\,1}{1\,\,0\,0},\binom{-\,3\,2}{1\,\,0\,0},$
$\displaystyle\binom{-\,4\,0}{1\,\,1\,0},\binom{-\,4\,0}{2\,\,0\,0},\binom{-\,3\,1}{1\,\,1\,0},\binom{-\,3\,1}{2\,\,0\,0},\binom{-\,3\,0}{3\,\,0\,0},\binom{-\,2\,1}{3\,\,0\,0},\binom{-\,2\,0}{2\,\,1\,1},\binom{-\,2\,0}{2\,\,2\,0},$
$\displaystyle\binom{-\,2\,0}{4\,\,0\,0},\binom{-\,1\,1}{3\,\,1\,0},\binom{-\,1\,0}{2\,\,2\,1},\binom{-\,1\,0}{3\,\,1\,1},\binom{-\,1\,0}{5\,\,0\,0},\binom{-\,0\,0}{3\,\,2\,1},\binom{-\,0\,0}{4\,\,2\,0},\binom{-\,0\,0}{5\,\,1\,0},$
$\displaystyle\binom{-\,2\,1\,0}{1\,\,1\,0\,0},\binom{-\,2\,0\,0}{2\,\,1\,0\,0},\binom{-\,1\,1\,0}{2\,\,1\,0\,0},\binom{-\,1\,0\,0}{2\,\,1\,1\,0},\binom{-\,1\,0\,0}{3\,\,1\,0\,0}\bigg{\\}}.$
$\text{GFP}_{D_{2},D_{2},-1,5}(8)=\left\\{\binom{-\,3\,0}{2\,\,1\,0},\binom{-\,2\,1}{2\,\,1\,0},\binom{-\,2\,0}{3\,\,1\,0},\binom{-\,1\,0}{3\,\,2\,0},\binom{-\,1\,0}{4\,\,1\,0}\right\\}.$

## References

  * [1] G. Andrews. ``Generalized Frobenius partitions", American Mathematical Society, Volume 49, Number 301, (1984).
  * [2] M. Balázs. ``Growth fluctuations in a class of deposition models", Ann. Inst.H. Poincaré Probab. Statist., Volume 39, Issue 4 (2003) 639-685.
  * [3] M. Balázs and R. Bowen. ``Product blocking measures and a particle system proof of the Jacobi triple product ", Ann. Inst.H. Poincaré Probab. Statist., Volume 54, Number 1 (2018) 514-528.
  * [4] G.Carinci, C. Giardiná, F. Redig and T. Sasamoto. ``A generalized asymmetric exclusion process with $U_{q}(\mathfrak{sl}_{2})$ stochastic duality ", Probab. Theory Relat. Fields, 166: 887-933, (2016).
  * [5] J. Engländer and S. Volkov. ``Turning a coin over instead of tossing it", Journal of Theoretical Probability, 31(2):1097-1118, (2018).
  * [6] T. Liggett ``Interacting Particle Systems", Classics in Mathematics, Sprigner, (2005).