THE CHROMATICITY OF A FAMILY OF NONPLANAR GRAPHS

PENG Yan-ling

(Department of Mathematics,Suzhou University of Science and Technology,Suzhou 215009,China)

Abstract:In this paper,we study the chromaticity of a family of nonplanar graphs that are subdivisions of K3,3.By analysing the chromatic polynomial and the structure of a graph,we get the structure characteristics of graphs which have the same chromatic polynomials as K3,3-subdivision graphs’,which prompts the study of the chromaticity of nonplanar graphs.

Keywords:chromatic polynomial;K3,3-subdivision graph;chromatic equivalence;chromaticity of nonplanar graph

1 Introduction

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 K3,3or the subdivision of K5,the study on the chromaticity of subdivision of K3,3or K5may prompt the study of the chromaticity of general nonplanar graphs.In this paper,we explore the chromaticity of a family of K3,3-subdivision graphs,and characterize the structures of graphs which have the same polynomials as K3,3-subdivision graphs’.

The operation of replacing an edge of a graph by a path is called subdivision.A K3,3-subdivision is a subdivision of the nonplanar graph K3,3.In this paper,we consider K3,3-subdivision graphs obtained by subdividing only one edge of K3,3.Such a graph is denoted by,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 λ,let P(G;λ)denote the number of λ-colourings of the vertices of G.The P(G;λ)is a polynomial in λ,called the chromatic polynomial of G.Two graphs G and H are said to be chromatically equivalent if P(G;λ)=P(H;λ).

Figure 1

2 Auxiliary Results

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,λ)is divisible by(λ ? 1)2if 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 G1be the graph obtained from G by deleting the chain,and let G2be the graph obtained from G1by identifying the vertices X and Y.Then

3 Main Results

Lemma 3.1 Let G be chromatically equivalent to.Then we have

Proof Let G1be the graph obtained fromby deleting the chain of length l between vertices X and Y,and let G2be the graph obtained from G1by identifying the vertices X and Y(see Figure 2).

Figure 2

It is easy to get the chromatic polynomials of G1and G2as follows

Then by Proposition 2.3,we have

Remark 3.1 Since(λ ? 1)2P(G,λ),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,by Proposition 2.1,G is a graph with|V(G)|=l+5,|E(G)|=l+8,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≤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

which implies k?s≤6.

Let W be the subgraph of G induced by the edge set E(G)?E(H).Then V(W)∩V(H)≠? since otherwise G is disconnected.Since

we have

But

therefore k?s=6,forces

So,for any v∈ V(W)?V(H),we have degG(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,λ)=P(,λ)and H be the 4-cycle clique of G.Then the number of vertices v in H with degG(v)=2 is 0 or greater than 2.

Proof Since G is chromatically equivalent to,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 degG(v)=2,then by Lemma 3.2,we have k≤7.

Since G has 5 cycles of length 4 and no triangle,for k≤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 K3,3?e,which is G1as depicted in Figure 2.

Let W be the subgraph induced by the edge set E(G)?E(H).Then,V(W)∩V(H)≠ ? since otherwise G is disconnected.It is clear that

On the other hand,by hypothesis,there is only one vertex v in H with degG(v)=2,so we have

Therefore,

or

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 degG(v)=3,where v∈V(W)?V(H).Then

So x=1,which means that there is only one vertex v in the set V(W)?V(H)with degG(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

Thus,for any v∈V(W)?V(H),we have degG(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 degH(u)=2,and another one must be attached to H at a vertex,say v,and degH(v)=3.If u is adjacent to v,then G is isomorphic to the graph G3shown in Figure 3.If u and v are nonadjacent,then G is isomorphic to the graph G4(see Figure 3).

Figure 3

By Proposition 2.3,we have

and

both of which are not equal to P(G,λ),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 H1shown in Figure 4.

Figure 4

Since V(H)=7 and there is only one vertex v in H with degG(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

but

a contradiction.

Therefore,the number of vertices v in H with degG(v)=2 is 0 or greater than 2.

Theorem 3.2 Let G be a graph with P(G,λ)=P(,λ).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

But(λ2? 3λ +3)P(G,λ)(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(λ2? 3λ +3)P(G,λ).

Let λ2? 3λ +3=f(λ)=f.By Lemma 3.1,we know that

Since

and(?1)lλ(λ ?1)(λ ? 2)(λ2? 5λ +7)≡ (?1)l2λ(λ ? 1)(λ ? 1)(modf),we have

Suppose P(G,λ)≡ 0(modf),then,since the g.c.d(λ(λ ? 1),f(λ))=1,we have

i.e.,

However,by(*),we have l≡2(mod 3)and in turn l(l?1)/2?2≡2(2?1)/2?2≡?1≡2(mod 3),a contradiction to(**).

Theorem 3.3 Let G be a graph with P(G,λ)=P(,λ)and H be the 4-cycle clique of G.If degG(v)≥3 for any v∈V(H),then G is isomorphism to

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

but

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 degG(v)≥3 for any v∈V(H),both of the end vertices of the chain must be attached to H at the vertices X and Y,respectively,and degH(X)=degH(Y)=2.Thus we see that G is isomorphism to

Problem Let G be a graph with P(G,λ)=P(,λ).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.