Bounds for DP Color Function and Canonical Labelings

Abstract

The DP-coloring is a generalization of the list coloring, introduced by Dvořák and Postle. Let ${\mathcal {H}}=(L,H)$ be a cover of a graph G and $P_{DP}(G,{\mathcal {H}})$ be the number of ${\mathcal {H}}$-colorings of G. The DP color function $P_{DP}(G,m)$ of G, introduced by Kaul and Mudrock, is the minimum value of $P_{DP}(G,{\mathcal {H}})$ where the minimum is taken over all possible m-fold covers ${\mathcal {H}}$ of G. For the family of n-vertex connected graphs, one can deduce that trees maximize the DP color function, from two results of Kaul and Mudrock. In this paper we obtain tight upper bounds for the DP color function of n-vertex 2-connected graphs. Another concern in this paper is the canonical labeling in a cover. It is well known that if an m-fold cover ${\mathcal {H}}$ of a graph G has a canonical labeling, then $P_{DP}(G,{\mathcal {H}})=P(G,m)$ in which P(G, m) is the chromatic polynomial of G. However the converse statement of this conclusion is not always true. We give examples that for some m and G, there exists an m-fold cover ${\mathcal {H}}$ of G such that $P_{DP}(G,{\mathcal {H}})=P(G,m)$, but ${\mathcal {H}}$ has no canonical labelings. We also prove that when G is a unicyclic graph or a theta graph, for each $m\ge 3$, if $P_{DP}(G,{\mathcal {H}})=P (G,m)$, then ${\mathcal {H}}$ has a canonical labeling.

1 Introduction

All graphs considered in this paper are finite and simple. The set of natural numbers is ${\mathbb {N}}=\{1,2,3,\ldots \}$. For $m\in {\mathbb {N}}$, let $[m]=\{1,\ldots ,m\}$. For any graph G, let V(G) and E(G) be its vertex set and edge set respectively. For any $v\in V(G)$, let $N_G(v)$ denote the set of neighbors of v in G and $d_G(v)$ denote the degree of v in G. A proper m-coloring of G is a mapping $c: V(G)\rightarrow [m]$ such that $c(u)\ne c(v)$ whenever $uv\in E(G)$. In 1912, Birkhoff [3] introduced a function P(G, m) which counts the number of proper m-colorings of G, it is a polynomial in m and called chromatic polynomial of G. The book by Dong, Koh and Teo [4] gives an overview for chromatic polynomial problems.

Since it is difficult to get a simple expression for the chromatic polynomial of an arbitrary graph, the bounds for the chromatic polynomials of graphs are of particular interest. For n-vertex connected graphs, the upper bound for their chromatic polynomials can be found in [4].

Theorem 1.1

[4, Theorem 15.3.2] Let G be a connected graph with n vertices. Then for all $m\in {\mathbb {N}}$,

$$\begin{aligned} P(G, m)\le m(m-1)^{n-1}, \end{aligned}$$

where equality holds for $m\ge 3$ if and only if G is a tree.

For the family of 2-connected graphs, Tomescu obtained the following result.

Theorem 1.2

[20, Theorem 2.1] Let G be a 2-connected graph with n vertices, where $n\ge 3$. Then for all $m\in {\mathbb {N}}$ with $m\ge 3$,

$$\begin{aligned} P(G,m)\le (m-1)^n+(-1)^n(m-1), \end{aligned}$$

where equality holds if and only if $G\cong C_{n}$; or $G\cong K(2,3)$ for the case that $n=5$ and $m=3$.

In [10], Felix gave a survey on the upper bounds for the chromatic polynomials of graphs of given order and size. Recently, some authors focus on the upper bounds for the chromatic polynomials of n-vertex graphs with chromatic number k, they obtained some inspired results, see [7,8,9, 11, 16, 17] for example.

In this paper we obtain analogous results to that in Theorems 1.1 and 1.2, in the context of DP-coloring. The DP-coloring (also called corresponding coloring) is a generalization of the list coloring, introduced by Dvořák and Postle [6].

Definition 1.3

[6] Let G be a graph. If $X,Y\subseteq V(G)$, we use G[X] for the subgraph of G induced by X, and we use $E_{G}(X,Y)$ for the subset of E(G) with one endpoint in X and one endpoint in Y. Given a set S, ${\mathcal {P}}(S)$ is the power set of S.

• A cover of a graph G is a pair ${\mathcal {H}}=(L,H)$ consisting of a graph H and a function $L: V(G)\rightarrow {\mathcal {P}}(V(H))$ satisfying the following four requirements:

  • 1. the set $\{L(u):u\in V(G)\}$ is a partition of V(H);

  • 2. for every $u\in V(G)$, the graph H[L(u)] is complete;

  • 3. if $E_{H}(L(u),L(v))$ is nonempty, then $u=v$ or $uv\in E(G)$;

  • 4. if $uv\in E(G)$, then $E_{H}(L(u),L(v))$ is a matching (the matching may be empty).

• A cover ${\mathcal {H}}=(L,H)$ is m-fold if $\vert L(u)\vert =m$ for each $u\in V(G)$, and ${\mathcal {H}}$ is full if for each $uv\in E(G)$, $E_{H}(L(u),L(v))$ is a perfect matching.

• An ${\mathcal {H}}$-coloring of G is an independent set in H of size $\vert V(G)\vert$.

• The DP-chromatic number of G, denoted by $\chi _{DP}(G)$, is the smallest $m\in {\mathbb {N}}$ such that G admits an ${\mathcal {H}}$-coloring for every m-fold cover ${\mathcal {H}}$ of G.

In 2021, Kaul and Mudrock [14] gave the definition of DP color function.

Definition 1.4

[14] Let ${\mathcal {H}}=(L,H)$ be a cover of a graph G. We denote $P_{DP}(G,{\mathcal {H}})$ the number of ${\mathcal {H}}$-colorings of G. The DP color function of G, denoted by $P_{DP}(G,m)$, is the minimum value of $P_{DP}(G,{\mathcal {H}})$ where the minimum is taken over all possible m-fold covers ${\mathcal {H}}$ of G.

By the definition of chromatic polynomial and DP color function, $P_{DP}(G,m)\le P(G,m)$ holds for any graph G and $m\in {\mathbb {N}}$. Let ${\mathcal {H}}=(L,H)$ be an m-fold cover of a graph G. We say that ${\mathcal {H}}$ has a canonical labeling if it is possible to name the vertices of H so that $L(u)=\{(u,j):j\in [m]\}$ for each $u\in V(G)$ and $(u,j)(v,j)\in E(H)$ for each $j\in [m]$ whenever $uv\in E(G)$. It is well known that if ${\mathcal {H}}$ has a canonical labeling, then $P_{DP}(G,{\mathcal {H}})=P(G,m)$ holds for each $m\in {\mathbb {N}}$. So there is a natural question as following.

Question 1.5

Suppose that ${\mathcal {H}}=(L,H)$ is a full m-fold cover of a graph G and $P_{DP}(G, {\mathcal {H}})=P(G,m)$. Does ${\mathcal {H}}$ have a canonical labeling?

By finding two examples, we give a negative answer to this question. But, considering our examples are only for some small m, we have the following question.

Question 1.6

Suppose that ${\mathcal {H}}=(L,H)$ is a full m-fold cover of a graph G, does there exist some $M\in {\mathbb {N}}$ such that for each $m\ge M$, if $P_{DP}(G,{\mathcal {H}})=P(G,m)$, then ${\mathcal {H}}$ has a canonical labeling?

Question 1.6 is closely related to (but not equivalent to) the Problem 3 in [5]. In order to compare DP color functions with chromatic polynomials, Dong and Yang [5] defined a class of graphs called $\mathcal {DP^*}$. It denotes the set of graphs G for which there exists $M\in {\mathbb {N}}$ such that for every m-fold cover ${\mathcal {H}}=(L,H)$ of G, if ${\mathcal {H}}$ has no canonical labelings, then $P_{DP}(G,{\mathcal {H}})>P(G,m)$ holds for all $m\ge M$. Then, for each graph $G\in \mathcal {DP^*}$, $P_{DP}(G,m)=P(G,m)$ holds when $m\ge M$. And they posed the following question, i.e., the Problem 3 in [5].

Question 1.7

[5] For a graph G, is it true that if there exists an $M\in {\mathbb {N}}$ such that $P_{DP}(G,m)=P(G,m)$ holds for all $m\ge M$, then $G\in \mathcal {DP^*}$?

In [5], some types of graphs have been proved belonging to $\mathcal {DP^*}$. For example, if a graph G contains a spanning tree T such that for each $e\in E(G){\setminus } E(T)$, $\ell (e)$ is odd and e is contained in a cycle C of length $\ell (e)$ with the property that $\ell (e')<\ell (e)$ holds for each $e'\in E(C){\setminus } (E(T)\cup \{e\})$, then $G\in \mathcal {DP^*}$, where $\ell (e)=\infty$ if e is a bridge of G, and $\ell (e)$ is the length of a shortest cycle in G containing e otherwise. By the definition of $\mathcal {DP^*}$, we have the following result.

Proposition 1.8

If a graph $G\in \mathcal {DP^*}$, then there exists an $M\in {\mathbb {N}}$ such that for any full m-fold cover ${\mathcal {H}}$ of G with $P_{DP}(G,{\mathcal {H}})=P(G,m)$, where $m\ge M$, ${\mathcal {H}}$ has a canonical labeling.

In Sect. 2, we obtain tight upper bounds for the DP color function of n-vertex 2-connected graphs, and give two new proofs for the upper bounds for the DP color function of n-vertex connected graphs. In Sect. 3, we give two examples that $P_{DP}(G,{\mathcal {H}})=P(G,m)$ but ${\mathcal {H}}$ has no canonical labelings, and also give positive answers to Question 1.6 for unicyclic graphs and theta graphs.

We also note that Kaul, Mudrock, and their coauthors obtain lots of results on DP color function, see [2, 12, 13, 15, 18, 19] for example, they study the asymptotics of $P(G,m)-P_{DP}(G,m)$ for a fixed graph G, they develop techniques to evaluate $P_{DP}(G,m)$ for some classes of graphs such as chordal graphs, unicyclic graphs, theta graphs, Cartesian product graphs, joint graphs, vertex-gluings graphs, and clique-gluings graphs, etc. Zhang and Dong [22] give some sufficient conditions for graphs belong to $DP_{\approx }$ ($DP_{<}$, respectively) where $DP_{\approx }$ ($DP_{<}$, respectively) is the set of graphs G for which there exists an $M\in {\mathbb {N}}$ such that $P_{DP}(G,m)=P(G,m)$ ($P_{DP}(G,m)<P(G,m)$, respectively) holds for all $m\ge M$. Their results extend Dong and Yang’s results in [5].

2 Bounds for DP Color Function of 2-Connected Graphs

In [14], the authors obtained an upper bound for the DP color function of an arbitrary graph, by using a probabilistic argument.

Lemma 2.1

[14] For any graph G and all $m\in {\mathbb {N}}$,

$$\begin{aligned} P_{DP}(G,m)\le \frac{m^{|V(G)|}(m-1)^{|E(G)|}}{m^{|E(G)|}}. \end{aligned}$$

For a connected graph, Kaul and Mudrock [14] gave the following result.

Lemma 2.2

[14] For any connected graph G and all $m\in {\mathbb {N}}$,

$$\begin{aligned} P_{DP}(G,m)=\frac{m^{|V(G)|}(m-1)^{|E(G)|}}{m^{|E(G)|}} \end{aligned}$$

if and only if G is a tree.

Combining Lemmas 2.1 and 2.2, one can obtain the following result easily.

Theorem 2.3

Let G be a connected graph with n vertices. Then for all $m\in {\mathbb {N}}$,

$$\begin{aligned} P_{DP}(G,m)\le m(m-1)^{n-1} \end{aligned}$$

where equality holds for $m\ge 2$ if and only if G is a tree.

By considering the effect of the edge or vertex deletion on the DP color function, we will give two new proofs for Theorem 2.3.

Theorem 2.4

Let G be a graph with n vertices and u, v be two distinct vertices in V(G) with $uv\not \in E(G)$. If $G'=G+\{uv\}$, then for all $m\in {\mathbb {N}}$,

$$\begin{aligned} P_{DP}(G',m)\le P_{DP}(G,m)\frac{m-1}{m}. \end{aligned}$$

Proof

Suppose that ${\mathcal {H}}=(L,H)$ is an arbitrary full m-fold cover of G. Let $L'=L$ and $H'=H+E(L(u),L(v))$ where E(L(u), L(v)) is a perfect matching between L(u) and L(v) chosen uniformly at random from the m! possible perfect matchings, then $\mathcal {H'}=(L',H')$ is a full m-fold cover of $G'$. Let $t=P_{DP}(G,{\mathcal {H}})$ and ${\mathcal {I}}=\{I_1,\ldots ,I_{t}\}$ be the set of all ${\mathcal {H}}$-colorings of G.

For each $i\in [t]$, let $E_i$ be the event that $I_i$ is also an $\mathcal {H'}$-coloring of $G'$. When $I_i\cap L(u)$ is not adjacent to $I_i\cap L(v)$ in $H'$, the event $E_i$ occurs, so

$$\begin{aligned} Pr[E_i]=1-\frac{1}{m}. \end{aligned}$$

Let $X_i$ be the random variable that is one if $E_i$ occurs and zero otherwise. Let $X=\sum _{i=1}^{t}X_i$, then X is the random variable which equals $P_{DP}(G',\mathcal {H'})$. By the linearity of expectation, the expectation of X is

$$\begin{aligned} E[X]=\sum \limits _{i=1}^{t}E[X_i]=P_{DP}(G,{\mathcal {H}})\left( 1-\frac{1}{m}\right) . \end{aligned}$$

Then, combining the arbitrariness of ${\mathcal {H}}=(L,H)$, we have

$$\begin{aligned} P_{DP}(G',m)\le P_{DP}(G,m)\frac{m-1}{m}. \end{aligned}$$

The proof is complete. $\square$

Corollary 2.5

Let G be a graph with n vertices and u, v be two distinct vertices in V(G) with $uv\not \in E(G)$. If $G'=G+\{uv\}$, then for all $m\in {\mathbb {N}}$ and $m\ge \max \{2,\chi _{DP}(G)\}$,

$$\begin{aligned} P_{DP}(G',m)< P_{DP}(G,m). \end{aligned}$$

Proof

When $m\ge \max \{2,\chi _{DP}(G)\}$, we have $0<1-1/m<1$ and $P_{DP}(G,m)>0$, the corollary is straightforward from Theorem 2.4. $\square$

By using Corollary 2.5, we give a new proof of Theorem 2.3 as follow.

proof of Theorem 2.3

Let T be a spanning tree of G, then $P_{DP}(T,m)=m(m-1)^n$ for all $m\in {\mathbb {N}}$. From Proposition 2.3 in [1], $\chi _{DP}(G)\le 2$ if and only if G is a tree. We discuss the two cases as follow.

• Case 1 $|E(T)|=|E(G)|$. In this case, $G\cong T$, $P_{DP}(G,m)=m(m-1)^{n-1}$ for all $m\in {\mathbb {N}}$.

• Case 2 $|E(T)|<|E(G)|$. In this case G is not a tree, so $\max \{2,\chi _{DP}(G)\}=\chi _{DP}(G)\ge 3$.

When $m\ge \chi _{DP}(G)$, then $P_{DP}(G,m)< P_{DP}(T,m)$ from Corollary 2.5. When $2\le m< \chi _{DP}(G)$, then $P_{DP}(G,m)=0< m(m-1)^{n-1}$. When $m=1$, then $P_{DP}(G,m)=0\le m(m-1)^{n-1}$.

Summarizing the above, the theorem follows. $\square$

Theorem 2.6

Let G be a graph with n vertices, $w\in V(G)$ and $d_G(w)=d$, then for all $m\in {\mathbb {N}}$,

$$\begin{aligned} P_{DP}(G,m)\le m\left( 1-\frac{1}{m}\right) ^dP_{DP}(G-\{w\},m). \end{aligned}$$

Proof

Suppose that $\mathcal {H'}=(L',H')$ is an arbitrary full m-fold cover of $G-\{w\}$, and $N_G(w)=\{v_1,\ldots ,v_d\}$. Let $L(x)=L'(x)$ for all $x\in V(G-\{w\})$, $L(w)=\{(w,i): i\in [m]\}$, and $E(H)=E(H')\cup (\cup _{i=1}^{d}E_H(L(w),L(v_i)))$ where for each $i\in [d]$, $E_{H}(L(w),L(v_i))$ is a perfect matching between L(w) and $L(v_i)$ chosen uniformly at random from the m! possible perfect matchings for each $i\in [d]$, then ${\mathcal {H}}=(L,H)$ is a full m-fold cover of G. Let $\Omega$ be the family of all ${\mathcal {H}}=(L,H)$.

Let $t=P_{DP}(G-\{w\},\mathcal {H'})$ and $\mathcal {I'}=\{I_1',\ldots ,I_{t}'\}$ be the set of all $\mathcal {H'}$-colorings of $G-\{w\}$. In H, we denote $X(I_i')$ the number of vertices in L(w) that is not adjacent to any vertices in $I_i'$, then

$$\begin{aligned} P_{DP}(G, {\mathcal {H}})=\sum _{i=1}^{t}X(I_i'). \end{aligned}$$

Notice that $d_G(w)=d$, for each vertex $u\in L(w)$, in H the probability that u is not adjacent to any vertices in $I_i'$ is $(1-\frac{1}{m})^d$, so

$$\begin{aligned} E_{{\mathcal {H}}\in \Omega }[X(I_i')]=m\left( 1-\frac{1}{m}\right) ^d. \end{aligned}$$

Then, by the linearity of expectation, we have

$$\begin{aligned} E_{{\mathcal {H}}\in \Omega }[P_{DP}(G, {\mathcal {H}})]=\sum _{i=1}^{t}E_{{\mathcal {H}}\in \Omega }[X(I_i')]=m\left( 1-\frac{1}{m}\right) ^dP_{DP}(G-\{w\},\mathcal {H'}). \end{aligned}$$

Finally, combining the arbitrariness of $\mathcal {H'}=(L', H')$, we have

$$\begin{aligned} P_{DP}(G,m)\le m\left( 1-\frac{1}{m}\right) ^dP_{DP}(G-\{w\},m). \end{aligned}$$

The proof is complete. $\square$

By using Theorem 2.6, we give a new proof of Lemma 2.1, along with another new proof of Theorem 2.3 as follows.

Another proof of Theorem 2.3

Let $V(G)=\{v_1,\ldots ,v_n\}$, $G_n=G$, $G_i=G_{i+1}-\{v_{i+1}\}$ where $i\in [n-1]$, then $G_1$ is a graph with one vertex and no edges. By Theorem 2.6, for each $i\in [n-1]$, we have

$$\begin{aligned} P_{DP}(G_i,m)\le m\left( 1-\frac{1}{m}\right) ^{d_i}P_{DP}(G_{i-1},m), \end{aligned}$$

in which $d_i=d_{G_i}(v_i).$ Then,

$$\begin{aligned} P_{DP}(G,m)\le m^{n-1}\left( 1-\frac{1}{m}\right) ^{\sum _{i=2}^nd_i}P_{DP}(G_1,m)=m^n\left( 1-\frac{1}{m}\right) ^{\sum _{i=1}^nd_i}. \end{aligned}$$

For $\sum _{i=1}^nd_i=|E(G)|$, we have

$$\begin{aligned} P_{DP}(G,m)\le \frac{m^{\left| V(G)\right| }(m-1)^{\left| E(G)\right| }}{m^{\left| E(G)\right| }}. \end{aligned}$$

If G is a connected graph with n vertices, then $\mid E(G)\mid \ge n-1$, with equality holds if and only if G is a tree. Hence

$$\begin{aligned} P_{DP}(G,m)\le m(m-1)^{n-1}, \end{aligned}$$

combining with that $\chi _{DP}(G)\le 2$ if and only if G is a tree, the proof is complete. $\square$

Next we focus on the upper bounds of DP color function for 2-connected graphs.

An ear of a graph G is a maximal path whose internal vertices have degree 2 in G. An ear decomposition of G is a decomposition $Q_0,\ldots ,Q_k$ such that $Q_0$ is a cycle and $Q_i$ for $i\ge 1$ is an ear of $Q_0\cup \cdots \cup Q_{i-1}$. It is well known that every 2-connected graph has an ear decomposition.

Theorem 2.7

[21, Theorem 4.2.8] A graph is 2-connected if and only if it has an ear decomposition. Furthermore, every cycle in a 2-connected graph is the initial cycle in some ear decomposition.

In order to get the upper bound for the DP color function of 2-connected graphs, we first consider the DP color function of the graph obtained by adding an ear to a graph, then combine it with the ear decomposition of 2-connected graphs, the result follows.

Theorem 2.8

Let G be a graph with n vertices and u, v be two distinct vertices in V(G). If $G'$ is a graph obtained by adding an ear $uw_{1}\dots w_{l}v$ of length $l+1$ $(l\ge 0)$ to G, then for all $m\in {\mathbb {N}}$,

$$\begin{aligned} P_{DP}(G',m)\le P_{DP}(G,m)\frac{(m-1)^{l+1}}{m}. \end{aligned}$$

Proof

When $l=0$, the result follows from Theorem 2.4. We assume $l\ge 1$ in the following. Suppose that ${\mathcal {H}}=(L,H)$ is an arbitrary full m-fold cover of G in which $L(x)=\{(x,i):i\in [m]\}$ for each $x\in V(G)$. Let $G^*=G'-\{w_{l}v\}$, i.e., the graph $G^*$ is obtained by adding a path $P=uw_{1}\dots w_{l}$ to G. Let $L^*(x)=L(x)$ for each $x\in V(G^*)-\{w_1,\ldots , w_l\}$, $L^*(x)=\{(x,i):i\in [m]\}$ for each $x\in \{w_1,\ldots , w_l\}$, and

$$\begin{aligned} H^*=H+E(L^*(u),L^*(w_1))+\sum _{i=1}^{l-1}E(L^*(w_{i}),L^*(w_{i+1})) \end{aligned}$$

where $E(L^*(u),L^*(w_1))$ ($E(L^*(w_{i}),L^*(w_{i+1}))$, respectively) is a perfect matching between $L^*(u)$ and $L^*(w_1)$ ($L^*(w_i)$ and $L^*(w_{i+1})$, respectively) chosen uniformly at random from all possible perfect matchings, then $\mathcal {H^*}=(L^*,H^*)$ is a full m-fold cover of $G^*$.

From Proposition 21 in [14] and Lemma 19 in [2], one can get that

$$\begin{aligned} P_{DP}(G^*,\mathcal {H^*})=P_{DP}(G,{\mathcal {H}})(m-1)^{l}. \end{aligned}$$

From the arbitrariness of ${\mathcal {H}}=(L,H)$, we have

$$\begin{aligned} P_{DP}(G^*,m)= P_{DP}(G,m)(m-1)^{l}. \end{aligned}$$

Because $G'=G^*+\{w_{l}v\}$ and Theorem 2.4, we have

$$\begin{aligned} P_{DP}(G',m)\le P_{DP}(G^*,m)\frac{m-1}{m}= P_{DP}(G,m)\frac{(m-1)^{l+1}}{m}. \end{aligned}$$

The proof is completed. $\square$

In [14], Kaul and Mudrock computed the DP color function of the unicyclic graph (i.e., a connected graph containing exactly one cycle) with n vertices, so the DP color function of the cycle with n vertices can be deduced.

Lemma 2.9

[14, Theorem 11] Let $C_n$ be the cycle with n vertices.

• (i) If n is odd, then for all $m\in {\mathbb {N}}$,

  $$\begin{aligned} P_{DP}(C_n,m)=(m-1)^n-(m-1). \end{aligned}$$

• (i) If n is even, then for all $m\in {\mathbb {N}}$ and $m\ge 2$,

  $$\begin{aligned} P_{DP}(C_n,m)=(m-1)^n-1. \end{aligned}$$

Now we are ready to get a tight upper bound for the DP color function of 2-connected graphs.

Theorem 2.10

Let G be a 2-connected graph with n vertices and $G_0$ be a cycle of length $l_0$ in G.

• (i) If $G_0$ is an odd cycle, then for all $m\in {\mathbb {N}}$ and $m\ge 3$

  $$\begin{aligned} P_{DP}(G,m)\le (m-1)^n-(m-1)^{n-l_{0}+1}, \end{aligned}$$

  where equality holds if and only if $G\cong G_0$.

• (ii) If $G_0$ is an even cycle, then for all $m\in {\mathbb {N}}$ and $m\ge 3$,

  $$\begin{aligned} P_{DP}(G,m)\le (m-1)^n-(m-1)^{n-l_{0}}, \end{aligned}$$

  where equality holds if and only if $G\cong G_0$.

Proof

Since G is a 2-connected graph, G contains a cycle, and the DP-chromatic number of a cycle is three. From Theorem 2.7, G has an ear decomposition $Q_0,\ldots ,Q_k$ such that $Q_0\cong G_0$ is the cycle of length $l_0$ and $Q_i$ is an ear of $Q_0\cup \cdots \cup Q_{i-1}$ for $i\ge 1$. Suppose that ear $Q_i$ has length $l_i+1$ $(l_i\ge 0)$ for $1\le i\le k$, then we have $\sum _{i=0}^{k}l_{i}=n$.

By Theorems 2.8 and Lemma 2.9, if $G_0$ is an odd cycle,

$$\begin{aligned} P_{DP}(G,m)\le & {} P_{DP}(G_{0},m)\prod _{i=1}^{k}\frac{(m-1)^{l_{i}+1}}{m}\\= & {} \big ((m-1)^{l_{0}}-(m-1)\big )\frac{(m-1)^{n-l_{0}+k}}{m^k}\\= & {} \frac{(m-1)^{n+k}-(m-1)^{n-l_{0}+k+1}}{m^k}\\\le & {} \frac{(m-1)^{n+k}-(m-1)^{n-l_{0}+k+1}}{(m-1)^k}\\= & {} (m-1)^n-(m-1)^{n-l_{0}+1}, \end{aligned}$$

where the next to the last equalities hold if and only if $k=0$, i.e., $G\cong G_0$ is an n-vertex odd cycle. With a similar argument, if $G_0$ is an even cycle,

$$\begin{aligned} P_{DP}(G,m)\le & {} P_{DP}(G_{0},m)\prod _{i=1}^{k}\frac{(m-1)^{l_{i}+1}}{m}\\= & {} \big ((m-1)^{l_{0}}-1\big )\frac{(m-1)^{n-l_{0}+k}}{m^k}\\= & {} \frac{(m-1)^{n+k}-(m-1)^{n-l_{0}+k}}{m^k}\\\le & {} \frac{(m-1)^{n+k}-(m-1)^{n-l_{0}+k}}{(m-1)^k}\\= & {} (m-1)^n-(m-1)^{n-l_{0}}, \end{aligned}$$

where equality holds if and only if $G\cong G_0$ is an n-vertex even cycle. The proof is completed. $\square$

Theorem 2.11

Let G be a 2-connected graph with n vertices.

• (i) If n is odd, then for all $m\in {\mathbb {N}}$ and $m\ge 3$,

  $$\begin{aligned} P_{DP}(G,m)\le (m-1)^n-(m-1), \end{aligned}$$

  where equality holds if and only if G is an odd cycle with n vertices.

• (ii) If n is even, then for all $m\in {\mathbb {N}}$ and $m\ge 3$,

  $$\begin{aligned} P_{DP}(G,m)\le (m-1)^n-1, \end{aligned}$$

  where equality holds if and only if G is an even cycle with n vertices.

Proof

Because every 2-connected graph contains a cycle, the theorem follows from Theorem 2.10. $\square$

3 Canonical Labelings of ${\mathcal {H}}$

We begin this section by giving examples which gives negative answer to Question 1.5. Next we introduce some conclusions in [14] that will be used in our later proof, then we give positive answer to Question 1.6 for two types of graphs.

Let G and H be two vertex disjoint graphs, the join $G\vee H$ of G and H is obtained from $G\cup H$ by joining every vertex of G to every vertex of H. The join $C_{n}\vee K_1$ of a cycle with n vertices $C_n$ and a single vertex is called a wheel with n spokes and denoted $W_n$. A theta graph $\theta (r,s,t)$ $(r\ge 1, s,t\ge 2)$ is a graph obtained by joining two vertices by three internally disjoint paths of lengths r, s and t. For the wheel graph, unicyclic graph, cycle graph and theta graph, their chromatic polynomials can be found in [4].

Lemma 3.1

[4]

• (i) For the wheel $W_n$ $(n\ge 3)$,

  $$\begin{aligned} P(W_n,m)=m((m-2)^n+(-1)^n(m-2)). \end{aligned}$$

• (ii) For a unicyclic graph G with n vertices containing a cycle $C_i$ $(i\ge 3)$,

  $$\begin{aligned} P(G,m)=(m-1)^{n}+(-1)^i(m-1)^{n-i+1}. \end{aligned}$$

• (iii) For the n-cycle $C_n$ $(n\ge 3)$,

  $$\begin{aligned} P(C_n,m)=(m-1)^{n}+(-1)^n(m-1). \end{aligned}$$

• (iv) For the theta graph $\theta (r,s,t)$ $(r\ge 1, s,t\ge 2)$,

  $$\begin{aligned}{} & {} P(G,m)=\frac{(m-1)^{r+s+t}+(-1)^{s+t}(m-1)^{r+1}+(-1)^{r+t}(m-1)^{s+1}}{m}\\{} & {} +\frac{(-1)^{r+s}(m-1)^{t+1}+(-1)^{r+s+t}(m-1)^2+(-1)^{r+s+t+1}(m-1)}{m}. \end{aligned}$$

In a cover ${\mathcal {H}}=(L,H)$ of a graph G, the cross-edges are the edges of H connecting distinct parts of the partition $\{L(v):v\in V(G)\}$, we denote $E_c$ the set of all cross-edges in H, and denote $H[E_c]$ the edge-induced subgraph of H induced by $E_c$.

Example 3.2

Let ${\mathcal {H}}_1=(L_1,H_1)$ be a 3-fold cover of $W_4$, $V(W_4)=\{x,y,z,u,v\}$ and $L_1(w)=\{(w,i):i\in [3]\}$ for each $w\in V(W_4)$. If $H_1[E_c]$ is the graph as shown in Fig. 1, then $P_{DP}(W_4,{\mathcal {H}}_1)=P(W_4,3)=6$. We list all ${\mathcal {H}}_1$-colorings as follows,

$$\begin{aligned} \{(x,1),(u,2),(y,3),(v,2),(z,2)\},&\quad \{(x,2),(u,1),(y,3),(v,1),(z,1)\},\\ \{(x,3),(u,1),(y,2),(v,1),(z,1)\},&\quad \{(x,1),(u,3),(y,2),(v,3),(z,3)\},\\ \{(x,2),(u,3),(y,1),(v,3),(z,3)\},&\quad \{(x,3),(u,2),(y,1),(v,2),(z,2)\}. \end{aligned}$$

But clearly ${\mathcal {H}}_1$ has no canonical labelings.

Example 3.3

Let ${\mathcal {H}}_2=(L_2,H_2)$ be a 4-fold cover of $W_4$, $V(W_4)=\{x,y,z,u,v\}$ and $L_2(w)=\{(w,i):i\in [4]\}$ for each $w\in V(W_4)$. If $H_2[E_c]$ is the graph as shown in Fig. 2, then $P_{DP}(W_4,{\mathcal {H}}_2)=P(W_4,4)=72$. We list 18 of them that are all ${\mathcal {H}}_2$-colorings containing (x, 1) as follows,

$$\begin{aligned} \{(x,1),(u,2),(y,3),(v,2),(z,1)\},&\quad \{(x,1),(u,2),(y,3),(v,2),(z,4)\},\\ \{(x,1),(u,2),(y,3),(v,4),(z,1)\},&\quad \{(x,1),(u,2),(y,3),(v,4),(z,2)\},\\ \{(x,1),(u,2),(y,4),(v,2),(z,1)\},&\quad \{(x,1),(u,2),(y,4),(v,3),(z,1)\},\\ \{(x,1),(u,2),(y,4),(v,3),(z,2)\},&\quad \{(x,1),(u,3),(y,2),(v,3),(z,1)\},\\ \{(x,1),(u,3),(y,2),(v,4),(z,1)\},&\quad \{(x,1),(u,3),(y,2),(v,4),(z,3)\},\\ \{(x,1),(u,3),(y,4),(v,2),(z,1)\},&\quad \{(x,1),(u,3),(y,4),(v,2),(z,3)\},\\ \{(x,1),(u,3),(y,4),(v,3),(z,1)\},&\quad \{(x,1),(u,3),(y,4),(v,3),(z,2)\},\\ \{(x,1),(u,4),(y,2),(v,3),(z,4)\},&\quad \{(x,1),(u,4),(y,2),(v,4),(z,3)\},\\ \{(x,1),(u,4),(y,3),(v,2),(z,4)\},&\quad \{(x,1),(u,4),(y,3),(v,4),(z,2)\}. \end{aligned}$$

But ${\mathcal {H}}_2$ has no canonical labelings.

Fig. 1

The subgraph $H_1[E_c]$

Fig. 2

The subgraph $H_2[E_c]$

We note that in the above two examples $m=3$ or 4, and we can’t extend m to larger one for the graph $W_4$. So we consider whether Question 1.6 has a positive answer for each graph. In fact, there are some types of graphs, for which Question 1.6 has a positive answer.

Proposition 3.4

[14] If T is a tree and ${\mathcal {H}}=(L,H)$ is a full m-fold cover of T where $m\ge 1$, then ${\mathcal {H}}$ has a canonical labeling.

In the following, we find two more examples to affirm Question 1.6.

Lemma 3.5

[14] Let G be a graph with $e=uv\in E(G)$. For each $(i,j)\in [m]\times [m]$, let $C_m^{(i,j)}$ be the set of proper m-coloring of $G-\{e\}$ that color u with i and v with j. Then,

• (i) there is an $r\in {\mathbb {N}}$ such that $|C_m^{(i,i)}|=r$ for each $i\in [m]$.

• (ii) there is a $t\in {\mathbb {N}}$ such that $|C_m^{(i,j)}|=t$ whenever $i\ne j$ and $i,j\in [m]$. Consequently, $mr=P(G-\{e\},m)-P(G,m)$ and $m(m-1)t=P(G,m)$.

From Lemma 3.5 and the definition of canonical labeling, we obtain the following lemma.

Lemma 3.6

Let G be a graph and ${\mathcal {H}}=(L,H)$ be a full m-fold cover of G with $m\ge 2$. Suppose $e\in E(G)$ and $e=uv$. Let $H'=H-E_H(L(u),L(v))$ so that $\mathcal {H'}=(L,H')$ is a full m-fold cover of $G-\{e\}$. For each $(i,j)\in [m]\times [m]$, let $\mathcal {H'}_{(i,j)}$ be the set of $\mathcal {H'}$-coloring that contain (u, i) and (v, j). If $\mathcal {H'}$ has a canonical labeling, then we have

• (i) when $i=j$,

  $$\begin{aligned} |\mathcal {H'}_{(i,j)}|=\frac{P(G-\{e\},m)-P(G,m)}{m}; \end{aligned}$$

• (ii) when $i\ne j$,

  $$\begin{aligned} |\mathcal {H'}_{(i,j)}|=\frac{P(G,m)}{m(m-1)}. \end{aligned}$$

  Furthermore, suppose $P=\{(i,j): (u,i)(v,j)\in E_H(L(u),L(v))\}$, then

  $$\begin{aligned} P_{DP}(G,{\mathcal {H}})=P_{DP}(G',\mathcal {H'})-\sum _{(i,j)\in P}|\mathcal {H'}_{(i,j)}|. \end{aligned}$$

Lemma 3.7

[14] Let G be a graph and $\mathcal {H}=(L,H)$ be a full m-fold cover of G with $m\ge 3$. Suppose $\alpha _1$ $\alpha _2$ $\alpha _3$ is a path of length two in G and $\alpha _1\alpha _3\notin E(G)$. Let $e_1=\alpha _1\alpha _2$, $e_2=\alpha _2\alpha _3$. Then, let $G_0=G-\{e_1, e_2\}$, $G_1=G-\{e_1\}$, $G_2=G-\{e_2\}$, and $G^*$ be the graph obtained from G by adding an edge between $\alpha _1$ and $\alpha _3$. Let $H'=H-(E_H(L(\alpha _1), L(\alpha _2))\cup E_H(L(\alpha _2), L(\alpha _3)))$ so that $\mathcal {H'}=(L,H')$ is an m-fold cover of $G_0$. Suppose that $\mathcal {H'}$ has a canonical labeling. Let

$$\begin{aligned} A_1= & {} P(G_0,m)-P(G,m),\\ A_2= & {} P(G_0,m)-P(G_2,m)+\frac{1}{m-1}P(G,m),\\ A_3= & {} P(G_0,m)-P(G_1,m)+\frac{1}{m-1}P(G,m),\\ A_4= & {} \frac{1}{m-1}(P(G_1,m)+P(G_2,m)+P(G^*,m)-P(G,m)), and\\ A_5= & {} \frac{1}{m-1}(P(G_1,m)+P(G_2,m)-\frac{1}{m-2}P(G^*,m)).\\ \end{aligned}$$

Then,

$$\begin{aligned} P_{DP}(G,{\mathcal {H}})\ge P(G_0,m)-\max \{A_1, A_2, A_3, A_4, A_5\}. \end{aligned}$$

Moreover, there exists an m-fold cover of G, $\mathcal {H^*}$, such that

$$\begin{aligned} P_{DP}(G,\mathcal {H^*})=P(G_0,m)-\max \{A_1, A_2, A_3, A_4, A_5\}. \end{aligned}$$

From Lemma 3.7 and its proof in [14], we get Lemma 3.8.

Lemma 3.8

Under the condition of Lemma 3.7. Let $H''$ be the graph with $V(H'')=\bigcup _{i=1}^{3}L(\alpha _i)$ and $E(H'')=E_H(L(\alpha _1),L(\alpha _2))\cup E_H(L(\alpha _2),L(\alpha _3))$. Clearly $H''$ can be decomposed into m vertex disjoint paths on three vertices. Take any one of m paths, let it be $(\alpha _1,i)(\alpha _2,j)(\alpha _3,k)$ where $i,j,k\in [m]$, then we have five cases for i, j, k, that are (1) $i=j=k$, (2) $i=j$ and $j\ne k$, (3) $i\ne j$ and $j=k$, (4) $i\ne j$ and $i=k$, (5) i, j, k are pairwise distinct. Let $\mathcal {H'}_{(i,j,k)}$ be the set of $\mathcal {H'}$-coloring that contains at least one edge of the path $(\alpha _1,i)(\alpha _2,j)(\alpha _3,k)$. Then $|\mathcal {H'}_{(i,j,k)}|=A_q/m$ when i, j, k satisfy case q, $(1\le q\le 5)$. Furthermore, we suppose that for $q\in [5]$, there are $m_q$ paths of case q in the m paths. Then $\sum _{q=1}^{5}m_q=m$ and

$$\begin{aligned} P_{DP}(G,{\mathcal {H}})=P(G_0,m)-\frac{1}{m}\sum \limits _{q=1}^{5}m_qA_q. \end{aligned}$$

Theorem 3.9

Let G be a unicyclic graph with n vertices containing a cycle C on g vertices where $g\ge 3$ and ${\mathcal {H}}=(L,H)$ be a full m-fold cover of G. For each $m\ge 2$, if $P_{DP}(G, {\mathcal {H}})=P(G,m)$, then ${\mathcal {H}}$ has a canonical labeling.

Proof

Suppose $e\in E(C)$ and $e=uv$. Let $G'=G-\{e\}$ and $\mathcal {H'}=(L,H')$ where $H'=H-E_H(L(u),L(v))$. Then, $G'$ is a tree and $\mathcal {H'}$ is a full m-fold cover of $G'$. Proposition 3.4 implies that $\mathcal {H'}$ has a canonical labeling. Let $P=\{(i,j): (u,i)(v,j)\in E_H(L(u),L(v))\}$, $P_1=\{(i,j)\in P\ \text{ and }\ i=j\}$, and $P_2=\{(i,j)\in P \ \text{ and }\ i\ne j\}$. Suppose that $|P_2|=t$, then $|P_1|=m-t$. By Lemma 3.6, we have that for $m\ge 2$

$$\begin{aligned} P_{DP}(G,{\mathcal {H}})= & {} P_{DP}(G',\mathcal {H'})-\sum _{(i,j)\in P}|\mathcal {H'}_{(i,j)}|\\= & {} P(G',m)-t\frac{P(G,m)}{m(m-1)}-(m-t)\frac{P(G',m)-P(G,m)}{m}. \end{aligned}$$

For $P(G,m)=(m-1)^{n}+(-1)^g(m-1)^{n-g+1}$ and $P(G',m)=m(m-1)^{n-1}$, we have

$$\begin{aligned} P_{DP}(G,{\mathcal {H}})=(m-1)^n+(-1)^g(m-t-1)(m-1)^{n-g}. \end{aligned}$$

If $P_{DP}(G, {\mathcal {H}})=P(G,m)$, then $t=0$ which implies ${\mathcal {H}}$ is a canonical labeling. $\square$

Theorem 3.10

Let $G=\theta (r,s,t)$ $(r\ge 1, s,t\ge 2)$ and ${\mathcal {H}}=(L,H)$ be a full m-fold cover of G. For each $m\ge 3$, if $P_{DP}(G,{\mathcal {H}})=P(G,m)$, then ${\mathcal {H}}$ has a canonical labeling.

Proof

Let $\alpha _2$ be one of the common ends of the three paths of G, let $\alpha _1$ and $\alpha _3$ be the vertices in the path of length s and t respectively, that are adjacent to $\alpha _2$. Clearly $\alpha _1\alpha _2\alpha _3$ is a path of length two in G and $\alpha _1\alpha _3\not \in E(G)$. We define $e_1, e_2, G_0, G_1, G_2, G^{*}, \mathcal {H'}, H''$ and $m_q (1\le q\le 5)$ as they are defined in the statement of Lemmas 3.7 and 3.8.

Then $G_0$ is a tree and $\mathcal {H'}=(L,H')$ is a full m-fold cover of $G_0$. By Proposition 3.4, $\mathcal {H'}$ has a canonical labeling. So we can name the vertices of H so that $L(x)=\{(x,j): j\in [m]\}$ for each $x\in V(H)$ and $(x,j)(y,j)\in E(H)$ for each $j\in [m]$ whenever $xy\in E(G_0)$.

By computing, we get that

$$\begin{aligned} P(G_0,m)= & {} m(m-1)^{r+s+t-2},\end{aligned}$$

(1)

$$\begin{aligned} P(G_1,m)= & {} (m-1)^{r+s+t-1}+(-1)^{r+t}(m-1)^s,\end{aligned}$$

(2)

$$\begin{aligned} P(G_2,m)= & {} (m-1)^{r+s+t-1}+(-1)^{r+s}(m-1)^t,\end{aligned}$$

(3)

$$\begin{aligned} P(G^*,m)= & {} \left\{ \begin{array}{ll} P(G,m)-P(\theta (r+1,s-1,t-1),m), &{}\quad \text{ when }~~ s\ge 3 ~\text{ or }~t\ge 3;\\ P(G,m)-P(C_{r+2},m), &{}\quad \text{ when }~~ s=t=2. \end{array} \right. \end{aligned}$$

(4)

By Lemmas 3.7 and 3.8, we have that

$$\begin{aligned}{} & {} P_{DP}(G,{\mathcal {H}}) = P(G_0,m)-\frac{1}{m}\sum \limits _{q=1}^{5}m_qA_q\nonumber \\{} & {} =\frac{m-m_1-m_2-m_3}{m}P(G_0,m)+\frac{(m-1)m_1-m_2-m_3+m_4}{m(m-1)}P(G,m)\nonumber \\{} & {} \quad +\frac{(m-1)m_3-m_4-m_5}{m(m-1)}P(G_1,m)+\frac{(m-1)m_2-m_4-m_5}{m(m-1)}P(G_2,m)\nonumber \\{} & {} \quad +\frac{m_5-(m-2)m_4}{m(m-1)(m-2)}P(G^*,m). \end{aligned}$$

(5)

For simplicity, we let $u=m-1$. Then combining Eqs. (1)–(5) with Lemma 3.1(iv), we have that when $s\ge 3$ or $t\ge 3$,

$$\begin{aligned}{} & {} P_{DP}(G,{\mathcal {H}})=\frac{u^{r+s+t+1}+u^{r+s+t}+(-1)^{r+t}(u^{s+2}+u^{s+1})+(-1)^{s+t}(u^{r+2}+u^{r+1})}{(u+1)^2}\nonumber \\{} & {} \quad +\frac{(-1)^{r+s}(u^{t+2}+u^{t+1})+(-1)^{r+t+1}(m_2+m_4+m_5)(u^{s+1}+u^s)}{(u+1)^2}\nonumber \\{} & {} \quad +\frac{(-1)^{s+t+1}(m_2+m_3+m_5)(u^{r+1}+u^r)+(-1)^{r+s+1}(m_3+m_4+m_5)(u^{t+1}+u^t)}{(u+1)^2}\nonumber \\{} & {} \quad +\frac{(-1)^{r+s+t}u^3+(-1)^{r+s+t+1}(m_2+m_3+m_4+m_5)u^2}{(u+1)^2}\nonumber \\{} & {} \quad +\frac{(-1)^{r+s+t}(m_5-1)u+(-1)^{r+s+t}(m_2+m_3+m_4+2m_5)}{(u+1)^2}; \end{aligned}$$

(6)

when $s=t=2$,

$$\begin{aligned}{} & {} P_{DP}(G,{\mathcal {H}})=\frac{u^{r+6}-u^{r+4}+u^{r+3}-u^{r+1}-(m_2+m_3+m_5)(u^{r+2}-u^{r})+(-1)^r2u^5}{(u+1)^2(u-1)}\nonumber \\{} & {} \quad +\frac{(-1)^{r+1}(m_2+m_3+2m_4+2m_5-1)u^4+(-1)^{r+1}(m_2+m_3+m_4+m_5+3)u^3}{(u+1)^2(u-1)}\nonumber \\{} & {} \quad +\frac{(-1)^{r}(2m_2+2m_3+3m_4+4m_5-1)u^2+(-1)^r(m_2+m_3+m_4+m_5+1)u}{(u+1)^2(u-1)}\nonumber \\{} & {} \quad +\frac{(-1)^{r+1}(m_2+m_3+m_4+2m_5)}{(u+1)^2(u-1)} \end{aligned}$$

(7)

and

$$\begin{aligned} P(G,m)= & {} P(G,u+1)\nonumber \\= & {} \frac{u^{r+s+t}+(-1)^{s+t}u^{r+1}+(-1)^{r+t}u^{s+1}+(-1)^{r+s}u^{t+1}}{u+1}\nonumber \\{} & {} +\frac{(-1)^{r+s+t}u^2+(-1)^{r+s+t+1}u}{u+1}. \end{aligned}$$

(8)

Let $f_1(u)$, $f_2(u)$ and g(u) be the numerator of the Eqs. (6)–(8) respectively. Let $h_1(u)=f_1(u)-(u+1)g(u)$ and $h_2(u)=f_2(u)-(u^2-1)g(u)$. Because g(u) is a polynomial, $P_{DP}(G,{\mathcal {H}})=P(G,m)$ if and only if $h_1(u)=0,$ when $s\ge 3$ or $t\ge 3$; $h_2(u)=0$ when $s=t=2$. In the following, we will prove that if $h_1(u)=0$ (or $h_2(u)=0$), then $m_1=m$, $m_2=m_3=m_4=m_5=0$, i.e., ${\mathcal {H}}$ has a canonical labeling. We discuss the two cases respectively.

Case 1. $s\ge 3$ or $t\ge 3$.

In this case

$$\begin{aligned} h_1(u)= & {} (-1)^{r+t+1}(m_2+m_4+m_5)(u^{s+1}+u^s) \\{} & {} +(-1)^{s+t+1}(m_2+m_3+m_5)(u^{r+1}+u^r)\\{} & {} +(-1)^{r+s+1}(m_3+m_4+m_5)(u^{t+1}+u^t) \\{} & {} +(-1)^{r+s+t+1}(m_2+m_3+m_4+m_5)u^2\\{} & {} +(-1)^{r+s+t}m_5u+(-1)^{r+s+t}(m_2+m_3+m_4+2m_5). \end{aligned}$$

If $h_1(u)$ is a zero polynomial, then each coefficient of the polynomial is zero. We note that $\sum _{q=1}^{5}m_q=m=u+1$ and $m_q\ge 0$ for each $q\in [5]$.

Firstly, we focus on the constant term of $h_1(u)$. If the constant term of $h_1(u)$ is zero, then $m_2+m_3+m_4+2m_5\equiv 0 ~(\bmod ~u)$, i.e., $m_2+m_3+m_4+2m_5=ku$. And $k\in \{0,1,2\}$, because $m_2+m_3+m_4+2m_5\in \left[ 0,2u+2\right]$. According to the value of k, we have the following three situations.

• S1: $k=0$, i.e., $m_2+m_3+m_4+2m_5=0$. Then we have $m_2=m_3=m_4=m_5=0$ and $m_1=m$.

• S2: $k=1$, i.e.,$m_2+m_3+m_4+2m_5=m-1$. Then we have $m_1=m_5+1$.

• S3: $k=2$, i.e.,$m_2+m_3+m_4+2m_5=2m-2$. Then we have $m+m_1-m_5=2$ which implies $m_1=0$, $m_5=m-2$, $m_2+m_3+m_4=2$; or $m_1=1$, $m_5=m-1$, $m_2=m_3=m_4=0$.

Clearly, in situation S1, $h_1(u)=0$ and ${\mathcal {H}}$ has a canonical labeling. In the following, we will prove that in situations S2 and S3, $h_1(u)$ is not a zero polynomial. We focus on the coefficient of u in $h_1(u)$ and discuss the following two subcases.

Subcase 1.1. $r\ge 2.$

In this subcase, if the coefficient of u in $h_1(u)$ is zero, then $m_5+1\equiv 0 ~(\bmod ~u)$ in situation S2, and $m_5+2\equiv 0 ~(\bmod ~u)$ in situation S3.

In situation S2, if $m_5+1\equiv 0 ~(\bmod ~u)$, then $m_5=u-1=m-2$, $m_1=m-1$, and $m_1+m_5=2\,m-3$. Because $\sum _{q=1}^{5}m_q=m$, we have $2\,m-3\le m$, then $m\le 3$. So $m_1=2, m_5=1$, but this will not happen, we can’t have only one path $(\alpha _1,i)(\alpha _2,j)(\alpha _3,k)$ where i, j, k are pairwise distinct.

In situation S3, if $m_5+2\equiv 0 ~(\bmod ~u)$, then $m_5=u-2=m-3$, this contradicts $m_5=m-2$ or $m_5=m-1$.

Subcase 1.2. $r=1.$

In this subcase, if the coefficient of u in $h_1(u)$ is zero, then $m_2+m_3+2m_5+1\equiv 0 ~(\bmod ~u)$ in situation S2, and $m_2+m_3+2m_5+2\equiv 0 ~(\bmod ~u)$ in situation S3.

In situation S2, if $m_2+m_3+2m_5+1\equiv 0 ~(\bmod ~u)$, then $m_2+m_3+2m_5=u-1$, combining this with $m_2+m_3+m_4+2m_5=u$, $m_4=1$ follows. But when $m_4=1$, the coefficient of the leading term is not zero.

In situation S3, $m_5=m-2$ or $m-1$. If $m_5=m-2$ and $m_2+m_3+2m_5+2\equiv 0 ~(\bmod ~u)$, then $m_2+m_3+2m_5=2u-2$. Combining this with $m_2+m_3+m_4=2$, we have $m_2=m_3=0$ and $m_4=2$. But when $m_4=2$, the coefficient of the leading term is not zero. If $m_5=m-1$, then $m_2+m_3+2m_5=2u$, $m_2+m_3+2m_5+2\ne 0 ~(\bmod ~u)$, otherwise $u=2$. But when $u=2$, we have $m_5=2$, $m_1=1$ and $m_2=m_3=m_4=0$. This will not happen, because we can’t have two paths $(\alpha _1,i)(\alpha _2,j)(\alpha _3,k)$ where i, j, k are pairwise distinct when $m=3$.

Hence, in Case 1, if $h_1(u)=0$, then $m_1=m, m_2=m_3=m_4=m_5=0$, i.e., ${\mathcal {H}}$ has a canonical labeling.

Case 2. $s=t=2$.

In this case

$$\begin{aligned} h_2(u)= & {} (-m_2-m_3-m_5)u^{r+2} \\{} & {} +(m_2+m_3+m_5)u^r+(-1)^{r+1}(m_2+m_3+2m_4+2m_5)u^4\\{} & {} +(-1)^{r+1}(m_2+m_3+m_4+m_5)u^3+(-1)^r(2m_2+2m_3+3m_4+4m_5)u^2\\{} & {} +(-1)^r(m_2+m_3+m_4+m_5)u+(-1)^{r+1}(m_2+m_3+m_4+2m_5). \end{aligned}$$

The proof is similar to that for Case 1. If the constant term of $h_2(u)$ is zero, then $m_2+m_3+m_4+2m_5\equiv 0 ~(\bmod ~u)$, which is the same with that in Case 1. So we have the same three situations S1, S2, S3 with that in Case 1. Clearly, in situation S1, $h_2(u)=0$ and ${\mathcal {H}}$ has a canonical labeling. In the following, we will prove that in situations S2 and S3, $h_2(u)$ is not a zero polynomial. We discuss the following two subcases.

Subcase 2.1. $r\ge 2.$

In situation S2,

$$\begin{aligned}{} & {} (-1)^r(m_2+m_3+m_4+m_5)u+(-1)^{r+1}(m_2+m_3+m_4+2m_5)\\{} & {} \quad =(-1)^{r}u^2+(-1)^{r+1}(m_5+1)u,\end{aligned}$$

and in situation S3,

$$\begin{aligned}{} & {} (-1)^r(m_2+m_3+m_4+m_5)u+(-1)^{r+1}(m_2+m_3+m_4+2m_5)\\{} & {} \quad =(-1)^{r}2u^2+(-1)^{r+1}(m_5+2)u.\end{aligned}$$

If the coefficient of u in $h_2(u)$ is zero, then $m_5+1\equiv 0 ~(\bmod ~u)$ in situation S2, and $m_5+2\equiv 0 ~(\bmod ~u)$ in situation S3, which are exactly the same with that in Subcase 1.1. So with the same argument in Subcase 1.1, we obtain that in situations S2 and S3, $h_2(u)$ is not a zero polynomial in Subcase 2.1.

Subcase 2.2. $r=1.$

If the coefficient of u in $h_2(u)$ is zero, then

$$\begin{aligned} (m_2+m_3+m_5)u-(m_2+m_3+m_4+m_5)u+ku=(k-m_4)u=0. \end{aligned}$$

In situation S2, $k=1$, so $m_4=1$; in situation S3, $k=2$, so $m_4=2$. But no matter $m_4$ is 1 or 2, the leading term of $h_2(u)$ will not be zero.

Hence, in Case 2, if $h_2(u)=0$, then $m_1=m, m_2=m_3=m_4=m_5=0$, i.e., ${\mathcal {H}}$ has a canonical labeling.

Summarizing Cases 1 and 2, the theorem is obtained. $\square$

By Theorems 3.9 and 3.10, we know that the answer of Question 1.6 is yes for unicyclic graphs and theta graphs when $m\ge 2$, and $m\ge 3$ respectively. Whether the answer of Question 1.6 is yes for all graphs is still wide open.