It is clear that distinct graphs may have the same chromatic polynomial. This prompts Read to raise the question: what is the necessary and sufficient condition for two graphs to be chromatically equivalent, that is, to have the same chromatic polynomial (see [1])? This question remains unsolved. However, since then many invariants under chromatic equivalence were found and various families of chromatically equivalent graphs and results on such graphs were obtained successively. The question on chromatic equivalence is termed as the chromaticity of graphs. This remains an active area of research.

In order to answer the question raised by Read, we need to investigate graphs including planar graphs and nonplanar graphs. Since every nonplanar graph contains either the subdivision of $K_{3, 3}$ or the subdivision of $K_5$, the study on the chromaticity of subdivision of $K_{3, 3}$ or $K_{5}$ may prompt the study of the chromaticity of general nonplanar graphs. In this paper, we explore the chromaticity of a family of $K_{3, 3}$-subdivision graphs, and characterize the structures of graphs which have the same polynomials as $K_{3, 3}$-subdivision graphs'.

The operation of replacing an edge of a graph by a path is called subdivision. A $K_{3, 3}$-subdivision is a subdivision of the nonplanar graph $K_{3, 3}$. In this paper, we consider $K_{3, 3}$-subdivision graphs obtained by subdividing only one edge of $K_{3, 3}$. Such a graph is denoted by $K^l_{3, 3}$, as shown in Figure 1, where $l$ is the length of the chain between vertices $X$ and $Y$. A chain in $G$ is a path of $G$ in which all vertices, except possibly the end vertices, have degree 2 in the graph $G$. The length of a chain will be the number of edges in it.

For a given simple graph $G$ and a positive integer $\lambda$, let $P(G;\lambda)$ denote the number of $\lambda$-colourings of the vertices of $G$. The $P(G;\lambda)$ is a polynomial in $\lambda$, called the chromatic polynomial of $G$. Two graphs $G$ and $H$ are said to be chromatically equivalent if $P(G;\lambda)=P(H ;\lambda)$.

In this section, we cite some known results used in the sequel.

Proposition 2.1 Let $G$ and $H$ be chromatically equivalent. Then

(1) $|V(G)|=|V(H)|$, $|E(G)|=|E(H)|$ (see Koh and Teo [2]);

(2) $G$ and $H$ have the same girth and the same number of cycles of length equal to their girth (see Xu [3]).

Proposition 2.2 (see Whitehead and Zhao [4]) $P(G, \lambda)$ is divisible by $(\lambda-1)^2$ if and only if $G$ has a cut-vertex.

Proposition 2.3 (see [5]) Let $X$ and $Y$ be two vertices of degree greater than 2 in a graph $G$ between which there is a chain of length $m$. Let $G_{1}$ be the graph obtained from $G$ by deleting the chain, and let $G_{2}$ be the graph obtained from $G_{1}$ by identifying the vertices $X$ and $Y$. Then $P(G, \lambda)=\frac{1}{\lambda(\lambda-1)}P(C_{m+1}, \lambda)P(G_{1}, \lambda)+(-1)^{m}P(G_{2}, \lambda)$.

Lemma 3.1 Let $G$ be chromatically equivalent to $K_{3, 3}^{l}$. Then we have

$\begin{array}{rcl} P(G, \lambda)&=&((\lambda-1)^{l+1}+(-1)^{l+1}(\lambda-1))(\lambda^{4}-7\lambda^{3}+21\lambda^{2}-30\lambda+17)\\ &&+(-1)^{l}\lambda(\lambda-1)(\lambda-2)(\lambda^{2}-5\lambda+7). \end{array} $

Proof Let $G_{1}$ be the graph obtained from $K_{3, 3}^{l}$ by deleting the chain of length $l$ between vertices $X$ and $Y$, and let $G_{2}$ be the graph obtained from $G_{1}$ by identifying the vertices $X$ and $Y$ (see Figure 2).

It is easy to get the chromatic polynomials of $G_{1}$ and $G_{2}$ as follows

$ \begin{array}{rcl} P(G_{1}, \lambda)&=&\lambda(\lambda-1)(\lambda^{4}-7\lambda^{3}+21\lambda^{2}-30\lambda+17), \\ P(G_{2}, \lambda)&=&\lambda(\lambda-1)(\lambda-2)(\lambda^{2}-5\lambda+7). \end{array} $

Then by Proposition 2.3, we have

$ \begin{array}{rcl} P(G, \lambda)&=&\frac{1}{\lambda(\lambda-1)}P(C_{l+1}, \lambda)P(G_{1}, \lambda)+(-1)^{l}P(G_{2}, \lambda)\\ &=&\frac{1}{\lambda(\lambda-1)}[(\lambda-1)^{l+1}+(-1)^{l+1}(\lambda-1)]\\ &&\times[\lambda(\lambda-1)(\lambda^{4}-7\lambda^{3}+21\lambda^{2}-30\lambda+17)]\\ &&+(-1)^l\lambda(\lambda-1)(\lambda-2)(\lambda^{2}-5\lambda+7)\\ &=&((\lambda-1)^{l+1}+(-1)^{l+1}(\lambda-1))(\lambda^{4}-7\lambda^{3}+21\lambda^{2}-30\lambda+17)\\ &&+(-1)^{l}\lambda(\lambda-1)(\lambda-2)(\lambda^{2}-5\lambda+7). \end{array} $

Remark 3.1 Since $(\lambda-1)^2 \nmid{P(G, \lambda)}$, by Proposition 2.2, $G$ has no cut-vertex. So $G$ has no vertex of degree 1. Furthermore, $G$ has no cut-edge.

Remark 3.2 Since $G$ is chromatically equivalent to $K_{3, 3}^{l}$, by Proposition 2.1, $G$ is a graph with $|V(G)|=l+5$, $|E(G)|=l+8$, ${\rm girth}=4$, and $G$ has 5 cycles of length 4.

Definition 3.1 Let $G$ be a connected graph. The $4$-cycle clique of $G$ is a subgraph of $G$ induced by the vertex set of all cycles of length 4 in $G$.

Lemma 3.2 Let $G$ be a graph with $n$ vertices, $n+3$ edges and $H$ be the $4$-cycle clique of $G$. Suppose that $G$ has no vertex of degree 1. If $H$ has $k$ vertices among which $s$ vertices have degree 2 in the graph $G$, then $k-s\leq 6$. Furthermore, if $k-s=6$, then $G$ can be obtained by attaching some cycles and/or the end vertices of some chains of edge-disjoint to $H$.

Proof Since $G$ has no vertex of degree 1 and $H$ has $k$ vertices among which $s$ vertices have degree 2 in the graph $G$, we have

$ \sum\limits_{v\in V(G)} \deg_{G}(v)=2n+6\geq 3(k-s)+2s+2(n-k)=k-s+2n, $

which implies $k-s\leq 6$.

Let $W$ be the subgraph of $G$ induced by the edge set $E(G)-E(H)$. Then $V(W)\cap V(H)\neq \emptyset$ since otherwise $G$ is disconnected. Since

$ \sum\limits_{v\in V(H)} \deg_{G}(v)\geq 3(k-s)+2s=3k-s, $

we have

$ \sum\limits_{v\in V(W)-V(H)} \deg_{G}(v)\leq 2n+6-3k+s=2n-2k+6+s-k. $

But

$ \sum\limits_{v\in V(W)-V(H)} \deg_{G}(v)\geq 2(n-k)=2n-2k, $

therefore $k-s=6$, forces

$ \sum\limits_{v\in V(W)-V(H)} \deg_{G}(v)=2n-2k. $

So, for any $v\in {V(W)-V(H)}$, we have $\deg_{G}(v)=2$, which implies that $W$ consists of some cycles and/or some chains of edge-disjoint. Thus, $G$ is isomorphic to a graph which is obtained by attaching some cycles and/or the end vertices of some chains of edge-disjoint to $H$.

Theorem 3.1 Let $G$ be a graph with $P(G, \lambda)=P(K_{3, 3}^{l}, \lambda)$ and $H$ be the $4$-cycle clique of $G$. Then the number of vertices $v$ in $H$ with $\deg_{G}(v)=2$ is 0 or greater than 2.

Proof Since $G$ is chromatically equivalent to $K_{3, 3}^{l}$, by Remark 3.2, $G$ is a graph with $n$ vertices, $n+3$ edges, girth 4, and 5 cycles of length 4. By Remark 3.1, $G$ has no vertex of degree 1, no cut-edge and no cut-vertex.

Let $|V(H)|=k$. Suppose that there is only one vertex $v$ in $H$ with $\deg_{G}(v)=2$, then by Lemma 3.2, we have $k\leq 7$.

Since $G$ has 5 cycles of length 4 and no triangle, for $k\leq 5$, it is impossible for 5 cycles of length 4 to share these $k$ vertices. So $k$ must be 6 or 7. There are two cases to consider.

Case 1 If $k=6$, then $H$ is a graph of vertices 6, which contains 5 cycles of length 4 and no triangle. So $H$ is isomorphic to $K_{3, 3}-e$, which is $G_{1}$ as depicted in Figure 2.

Let $W$ be the subgraph induced by the edge set $E(G)-E(H)$. Then, $V(W)\cap V(H)\neq \emptyset$ since otherwise $G$ is disconnected. It is clear that

$ \sum\limits_{v\in V(W)-V(H)} \deg_{G}(v)\geq 2(n-6)=2n-12. $

On the other hand, by hypothesis, there is only one vertex $v$ in $H$ with $\deg_{G}(v)=2$, so we have

$\sum\limits_{v\in V(W)-V(H)} \deg_{G}(v)\leq 2n+6-3(k-1)-2=2n-11. $

Therefore,

$ \sum\limits_{v\in V(W)-V(H)} \deg_{G}(v)=2n-11 $

or

$ \sum\limits_{v\in V(W)-V(H)} \deg_{G}(v)=2n-12. $

Suppose $\sum\limits_{v\in V(W)-V(H)} \deg_{G}(v)=2n-11$. If $\exists$ $v\in{V(W)-V(H)}$, such that $\deg_{G}(v)\geq 4$, then

$2n-11=\sum\limits_{v\in V(W)- V(H)} \deg_{G}(v)\geq 2(n-7)+4=2n-10, $

a contradiction. So there is no vertex in the set $V(W)- V(H)$, which has degree 4 in $G$.

Let $x$ be the number of vertices $v$ with $\deg_{G}(v)=3$, where $v\in {V(W)- V(H)}$. Then

$ \sum\limits_{v \in V(W) - V(H)} {{{\deg }_G}} (v) = 2n - 11 = 3x + 2(n - 6 - x). $

So $x=1$, which means that there is only one vertex $v$ in the set ${V(W)-V(H)}$ with $\deg_{G}(v)=3$, and others are of degree 2. Thus, unless $G$ has a cut-edge, the number of edges in $E(W)$ is greater than $n-4$, which contradicts the fact $|E(W)|=|E(G)|-|E(H)|=n+3-8=n-5$. So

$ \sum\limits_{v\in V(W)-V(H)} \deg_{G}(v)=2n-12. $

Thus, for any $v\in V(W)-V(H)$, we have $\deg_{G}(v)=2$, which shows that $W$ may consist of some cycles and/or some chains of edge-disjoint. But $|V(W)-V(H)|$ $=n-6$ and $|E(W)|=n-5$, so $W$ is a chain or a cycle. Since $G$ has no cut-vertex, $G$ isn't isomorphic to a graph obtained by attaching a cycle to $H$ at one vertex of $H$, and so $G$ is isomorphic to a graph obtained by attaching the end vertices of a chain to $H$.

By hypothesis, there is only one vertex in $H$ which has degree 2 in $G$. Therefore, one of the end vertices of the chain $W$ must be attached to $H$ at a vertex, say $u$, and $\deg_{H}(u)=2$, and another one must be attached to $H$ at a vertex, say $v$, and $\deg_{H}(v)=3$. If $u$ is adjacent to $v$, then $G$ is isomorphic to the graph $G_3$ shown in Figure 3. If $u$ and $v$ are nonadjacent, then $G$ is isomorphic to the graph $G_4$ (see Figure 3).

By Proposition 2.3, we have

$ \begin{array}{rcl} P(G_3, \lambda)&=&((\lambda-1)^{l+1}+(-1)^{l+1}(\lambda-1))(\lambda^{4}-7\lambda^{3}+21\lambda^{2}-30\lambda+17)\\ &&+(-1)^{l}\lambda(\lambda-1)(\lambda-2)(\lambda^{2}-4\lambda+5) \end{array} $

and

$ \begin{array}{rcl} P(G_4, \lambda)&=&((\lambda-1)^{l+1}+(-1)^{l+1}(\lambda-1))(\lambda^{4}-7\lambda^{3}+21\lambda^{2}-30\lambda+17)\\ &&+(-1)^{l}\lambda(\lambda-1)(\lambda^{3}-5\lambda^{2}+10\lambda-7), \end{array} $

both of which are not equal to $P(G, \lambda)$, a contradiction.

Case 2 If $k=7$, then $H$ is a graph of vertices 7, which contains 5 cycles of length 4 and no triangle. So $H$ is isomorphic to $H_1$ shown in Figure 4.

Since $V(H)=7$ and there is only one vertex $v$ in $H$ with $\deg_{G}(v)=2$, by Lemma 3.2, $G$ can be obtained by attaching some cycles and/or the end vertices of some chains of edge-disjoint to $H$. Thus, we have

$ \sum\limits_{v\in V(G)} \deg_{G}(v)\geq(3\times6+2)+2(n-7)+2=2n+8, $

but

$ \sum\limits_{v\in V(G)} \deg_{G}(v)=2n+6, $

a contradiction.

Therefore, the number of vertices $v$ in $H$ with $\deg_{G}(v)=2$ is 0 or greater than 2.

Theorem 3.2 Let $G$ be a graph with $P(G, \lambda)=P(K_{3, 3}^{l}, \lambda)$. If there exist at least two vertices in the 4-cycle clique of $G$ which have degree 2 in graph $G$, then any two such vertices in the 4-cycle clique are nonadjacent.

Proof Assume that there exist two adjacent vertices in the 4-cycle clique of $G$ which have degree 2 in graph $G$. Let $Q$ be the graph remaining after deleting these two adjacent vertices. By the fundamental reduction theorem of chromatic polynomial (see [1]), we have

$ P(G, \lambda)=(\lambda^{2}-3\lambda+3)P(Q, \lambda). $

But $(\lambda^{2}-3\lambda+3)\nmid P(G, \lambda)$(see the proof bellow), a contradiction. So any two vertices in the 4-cycle clique of $G$ which have degree 2 in graph $G$ are nonadjacent.

Now, we show that $(\lambda^{2}-3\lambda+3)\nmid P(G, \lambda)$.

Let $\lambda^{2}-3\lambda+3=f(\lambda)=f$. By Lemma 3.1, we know that

$ \begin{array}{rcl} P(G, \lambda)&=&((\lambda-1)^{l+1}+(-1)^{l+1}(\lambda-1))(\lambda^{4}-7\lambda^{3}+21\lambda^{2}-30\lambda+17)\\ &&+(-1)^{l}\lambda(\lambda-1)(\lambda-2)(\lambda^{2}-5\lambda+7). \end{array} $

Since

$ \begin{array}{ll} &(\lambda-1)^{l+1}+(-1)^{l+1}(\lambda-1)=\lambda(\lambda-1)\big(\sum\limits_{i=2}^{l}C_{l}^i(-1)^{l-i}\lambda^{i-1}+(-1)^{l-1}l\big), \\ &\lambda^4-7\lambda^3+21\lambda^2-30\lambda+17=(\lambda^2-4\lambda+6)(\lambda^2-3\lambda+3)-1\equiv-1\;(\text{mod}f)\end{array} $

and $(-1)^l\lambda(\lambda-1)(\lambda-2)(\lambda^2-5\lambda+7)\equiv (-1)^l2\lambda(\lambda-1)(\lambda-1)\;(\text{mod}f), $ we have

$ \begin{array}{ll}P(G, \lambda)& \equiv \Big(\lambda(\lambda-1)\big(\sum\limits_{i=2}^{l}C_{l}^i(-1)^{l-i}\lambda^{i-1}+(-1)^{l-1}l\big)\Big)(-1)\\ &\quad +(-1)^l2\lambda(\lambda-1)(\lambda-1)\;(\text{mod}f)\\ &\equiv\lambda(\lambda-1)\Big(\sum\limits_{i=3}^lC_l^i(-1)^{l+1-i}\lambda^{i-1}+C_l^2(-1)^{l-1}\lambda+(-1)^ll\\ &\quad+(-1)^l2\lambda+(-1)^{l+1}2 \Big)\;(\text{mod}f)\\ &\equiv \lambda(\lambda-1)\Big(\sum\limits_{i=3}^{l}C_{l}^i(-1)^{l+1-i}\lambda^{i-1}+(-1)^{l-1}(\frac{l(l-1)}2-2\big)\lambda\\ &\quad +(-1)^{l}(l-2) \Big)\;(\text{mod}f). \end{array} $

Suppose $P(G, \lambda)\equiv 0\;(\text{mod}f)$, then, since the g.c.d $(\lambda(\lambda-1), f(\lambda))=1$, we have

$ \sum\limits_{i=3}^{l}C_{l}^i(-1)^{l+1-i}\lambda^{i-1}+(-1)^{l-1}(\frac{l(l-1)}2-2\big)\lambda+(-1)^{l}(l-2)\equiv 0\;(\text{mod} f), $

i.e.,

$ \sum\limits_{i=3}^{l}C_{l}^i(-1)^{l+1-i}\lambda^{i-1}+(-1)^{l-1}(\frac{l(l-1)}2-2\big)\lambda+(-1)^{l}(l-2) =(\lambda^2-3\lambda+3)\sum\limits_{i=0}^ma_i\lambda^i, $

where $\sum\limits_{i=0}^ma_i\lambda^i$ is some polynomial of integer coefficients. Now, by comparing the coefficients of both sides, we have

$ \begin{equation} l-2\equiv 0\;(\text{mod}~3), \end{equation} $

(*)

$ \begin{equation} l(l-1)/2-2\equiv 0\;(\text{mod}~ 3).\end{equation} $

(**)

However, by (*), we have $l\equiv 2\;(\text{mod}~3)$ and in turn $l(l-1)/2-2\equiv 2(2-1)/2-2\equiv -1\equiv 2\;(\text{mod}~ 3)$, a contradiction to (**).

Theorem 3.3 Let $G$ be a graph with $P(G, \lambda)=P(K_{3, 3}^{l}, \lambda)$ and $H$ be the 4-cycle clique of $G$. If $\deg_{G}(v)\geq 3$ for any $v\in V(H)$, then $G$ is isomorphism to $K_{3, 3}^{l}$.

Proof Since $P(G, \lambda)=P(K_{3, 3}^{l}, \lambda)$, by Remark 3.2, $G$ has 5 cycles of length 4 and no triangle. Let $|V(H)|=k$. Since $\deg_{G}(v)\geq3$ for any $v\in V(H)$, $k\leq 6$ by Lemma 3.2. For $k\leq 5$, it is impossible for 5 cycles of length 4 to share these $k$ vertices. Thus, $k$ must be 6. Therefore $H$ is a 4-cycle clique of vertices 6, which has 5 cycles of length 4 and no triangle. So $H$ is isomorphic to $K_{3, 3}-e$ which is $G_{1}$ as depicted in Figure 2.

Furthermore, by Lemma 3.2, $G$ can be obtained by attaching some cycles and/or the end vertices of some chains of edge-disjoint to $H$. If attaching more than one cycle and/or chain to $H$, we have

$ \sum\limits_{v\in G} \deg_{G}(v)>(3\times4+2\times2)+2(n-6)+2=2n+6, $

but

$ \sum\limits_{v\in G} \deg_{G}(v)=2n+6, $

a contradiction. So $G$ is obtained by attaching only one cycle or one chain to $H$. If $G$ is obtained by attaching a cycle to $H$ at one vertex of $H$, then $G$ has a cut-vertex, a contradiction to Remark 3.1. Therefore $G$ is obtained by attaching the end vertices of one chain to $H$. Since $\deg_{G}(v)\geq 3$ for any $v\in V(H)$, both of the end vertices of the chain must be attached to $H$ at the vertices $X$ and $Y$, respectively, and $\deg_{H}(X)=\deg_{H}(Y)=2$. Thus we see that $G$ is isomorphism to $K_{3, 3}^{l}$.

Problem Let $G$ be a graph with $P(G, \lambda)=P(K_{3, 3}^{l}, \lambda)$. If there are at least two nonadjacent vertices in the 4-cycle clique of $G$ which have degree 2 in $G$, discuss the structure of graph $G$.