# Chromatic Classes of 2-Connected(n,n+4)-Graphs with Exactly Three Triangles and at Least Two Induced 4-Cycles

Authors: G. C. Lau; Y. H. Peng
Journal: ISRN Discrete Mathematics
 (2011)

---

## Abstract

For a graphG, let P(G,λ) be its chromatic polynomial. Two graphs G and H are chromatically equivalent, denoted G~H, if P(G,λ)=P(H,λ). A graph G is chromatically unique if P(H,λ)=P(G,λ) implies that H≅G. In this paper, we determine all chromatic equivalence
classes of 2-connected (n,n+4)-graphs with exactly three triangles and at least two induced 4-cycles. As a byproduct of these, we obtain various new families of χ-equivalent graphs and
χ-unique graphs.


---

## Body

## 1. Introduction

LetP(G), or simply P(G), denote the chromatic polynomial of a simple graph G. Two graphs G and H are chromatically equivalent (simply χ-equivalent), denoted G~H, if P(G)=P(H). A graph G is chromatically unique (simply χ-unique) if P(H)=P(G) implies that H≅G. Let 〈G〉 denote the equivalence class determined by the graph G under ~. Clearly, G is χ-unique if and only if 〈G〉={G}. A graph H is called a relative of G if there is a sequence of graphs G=H1,H2,…,Hk=H such that each Hi is a Kri-gluing of some graphs (say Xi and Yi) and that Hi+1 is obtained from Hi by forming another Kri-gluing of Xi and Yi for 1≤i≤k-1. We say H is a graph of typeG if H is a relative of G or H≅G. A family 𝒮 of graphs is said to be relative-closed (simply χr-closed) if(i)
no two graphs in𝒮 are relatives of each other,(ii)
for any graphG∈𝒮, P(H,λ)=P(G,λ) implies that H∈𝒮 or H is a relative of a graph in S.If𝒮 is a χr-closed family, then the chromatic equivalence class of each graph in 𝒮 can be determined by studying the chromaticity of each graph in 𝒮.IfG is a graph of order n and size m, we say G is an (n,m)-graph. The chromatic equivalence classes of 2-connected (n,n+i)-graph have been fully determined for i=0,1  in [1, 2] and partially determined for i=2,3  in [3–5]. Peng and Lau have also characterized and classified certain chromatic equivalence classes of 2-connected (n,n+4)-graph in [6, 7]. In [8], by using the idea of cyclomatic number, the authors obtained the χr-closed family of 2-connected (n,n+4)-graphs with exactly three triangles.In this paper, all the chromatic equivalence classes of 2-connected(n,n+4)-graphs with exactly three triangles and at least two induced C4s are determined. As a byproduct of these, we obtain various new families of χ-equivalent graphs and χ-unique graphs. The readers may refer to [9] for terms and notation used but not defined here.


## 2. Notation and Basic Results

LetCn (or n-cycle) be the cycle of order n. An induced 4-cycle is the cycle C4 without chord. The following are some useful known results and techniques for determining the chromatic polynomial of a graph. Throughout this paper, all graphs are assumed to be connected unless otherwise stated.Lemma 2.1 (Fundamental Reduction Theorem (Whitney [10])).
LetG be a graph and e an edge of G.  Then
(2.1)P(G)=P(G-e)-P(G⋅e),
where G-e is the graph obtained from G by deleting e, and G·e is the graph obtained from G by identifying the end vertices of e.LetG1 and G2 be graphs, each containing a complete subgraph Kp with p vertices. If G is a graph obtained from G1 and G2 by identifying the two subgraphs Kp, then G is called a Kp-gluing of G1 and G2. Note that a K1-gluing and a K2-gluing are also called a vertex-gluing and an edge-gluing, respectively.Lemma 2.2 (Zykov [11]).
LetG be a  Kr-gluing of  G1 and  G2. Then
(2.2)P(G)=P(G1)P(G2)P(Kr).
Lemma 2.2 implies that all Kr-gluings of G1 and G2 are χ-equivalent. It follows from Lemma 2.2 that if H is a relative of G, then H~G.The following conditions for two graphsG and H to be χ-equivalence are well known (see, e.g., [4]).Lemma 2.3.
LetG and  H be two  χ-equivalent graphs. Then  G and  H have, respectively, the same number of vertices, edges, and triangles. If both  G and  H do not contain  K4, then they have the same number of induced  C4s.A generalizedθ-graph is a 2-connected graph consisting of three edge-disjoint paths between two vertices of degree 3. All other vertices have degree two. These paths have lengths x, y and z, respectively, where x≥y≥z. The graph is of order x+y+z-1 and size x+y+z (see [2]). We will denote K2 as C2 for convenience.Lemma 2.4.
(2.3)(i)P(Cn)=(λ-1)n+(-1)n(λ-1),n≥2,(2.4)(ii)P(θx,y,z)={P(Cx+1)P(Cy+1)P(Cz+1)λ2(λ-1)2+P(Cx)P(Cy)P(Cz)λ2,ifz≠1,P(Cx+1)P(Cy+1)λ(λ-1)ifz=1.Lemma2.4(i) can be proved by induction while Lemma 2.4(ii) follows from Lemmas 2.1 and 2.2. For integers x, y, z, n, and λ, let us write (2.5)Qn(λ)=∑i=0n-2(-1)i(λ-1)n-2-i,Mx,y,z(λ)=Qx+1(λ)Qy+1(λ)Qz+1(λ)+(λ-1)2Qx(λ)Qy(λ)Qz(λ).
Note that when λ=1, we have Qn(1)=(-1)n and Mx,y,z(1)=(-1)x+y+z+1. Lemma 2.4 can then be written as the following lemma.Lemma 2.5 (see [4]).
(i)P(Cn)=λ(λ-1)Qn(λ) and (ii)P(θx,y,z)=λ(λ-1)Mx,y,z(λ).We also need the following lemma.Lemma 2.6 (Whitehead and Zhao [12]).
A graphG contains a cut-vertex if and only if  (λ-1)2∣P(G).Lemma2.6 also implies that if H~G, then H is 2-connected if and only if G is so.


## 3. Classification of Graphs

Letℱ be the χr-closed family of 2-connected (n,n+4)-graphs with three triangles and at least two induced C4s. In [8], we classified all the 31 types of graph F∈ℱ as shown in Figure 1.  Since the approach used to classify all the graphs F is rather long and repetitive, we will not discuss it here. The reader may refer to Theorems 1 and 3 in [8] for a detail derivation of the graphs.Figure 1
31 types of 2-connected (n,n+4)-graphs with exactly three triangles and at least two induced 4-cycles. The light lines of the graphs refer to the paths of indicated length.We are now ready to determine the chromaticity of all 31 types ofχr-closed family of 2-connected (n,n+4)-graphs having exactly 3 triangles and at least two induced C4s as shown in Figure 1. We first note that if H~Fi(1≤i≤31) in Figure 1, then H must be of type Fj(1≤j≤31) in Figure 1 as well. For convenience, we will say that the graph Fi, or any of its relatives, is of type (i).In what follows, we will useFi(α), instead of Fi, to denote a graph of type (i) that has a path of length α. We now present our main results in the following theorem.Theorem 3.1.
(1)H∈〈F1〉 if and only if H is of type F1.
(2)H∈〈F2(a)〉 if and only if H is of type F2(a).
(3)H∈〈F3〉 if and only if H is of type F3.
(4)H∈〈F4〉 if and only if H is of type F4.
(5)H∈〈F5〉 if and only if H is of type F5.
(6)H∈〈F6〉 if and only if H≅F6,F25 or H is of type F22(3).
(7)H∈〈F7〉 if and only if H≅F7,F21,F27 or H is of type F31.
(8)〈F8(b)〉={F8(b),F28(b)}.
(9)F9 is χ-unique.
(10)〈F10〉={F10,F29}.
(11)H∈〈F11〉 if and only if H is of type F11, F13(3), or F24.
(12)H∈〈F12〉 if and only if H is of type F12.
(13)H∈〈F13(c)〉 if and only if H is of type F13(c) for c≥4, and H∈〈F13(3)〉 if and only if H is of type F11,F13(3), or F24.
(14)H∈〈F14〉 if and only if H is of type F14 or F18(3).
(15)F15(d) is χ-unique for d≥3, and 〈F15(2)〉={F15(2),F31}.
(16)F16 is χ-unique.
(17)F17 is χ-unique.
(18)H∈〈F18(e)〉 if and only if H is of type F18(e) for e≥4, and H∈〈F18(3)〉 if and only if H is of type F14 or F18(3).
(19)H∈〈F19〉 if and only if H is of type F19.
(20)〈F20(f)〉={F20(f),F26(f)}.
(21)H∈〈F21〉 if and only if H≅F7, F21, F27 or H is of type F31.
(22)H∈〈F22(h)〉 if and only if H is of type F22(h) for h≥4, and H∈〈F22(3)〉 if and only if H≅F6,F25 or H is of type F22(3).
(23)H∈〈F23〉 if and only if H is of type F23.
(24)H∈〈F24〉 if and only if H is of type F11, F13(3), or F24.
(25)H∈〈F25〉 if and only if H≅F6,F25 or H is of type F22(3).
(26)〈F26(j)〉={F20(j),F26(j)}.
(27)H∈〈F27〉 if and only if H≅F7, F21, F27 or H is of type F31.
(28)〈F28(k)〉={F8(k),F28(k)}.
(29)〈F29〉={F10,F29}.
(30)〈F30〉={F15(2),F30}.
(31)H∈〈F31〉 if and only if H≅F7, F21, F27 or H is of type F31.


## 4. Chromatic Polynomials of the Graphs

Before proving our main result, we present here some useful information about the chromatic polynomial ofFi (1≤i≤31). Let W(n,k) denote the graph of order n obtained from a wheel Wn by deleting all but k consecutive spokes. Also let Wm(5,3) denote the graph obtained from W(5,3) by identifying the end-vertices of a path Pm to two non-adjacent degree 3 vertices of W(5,3). Using Software Maple or Lemmas 2.1, 2.2 and 2.5, it is easy to obtain the chromatic polynomial of each graph in ℱ as shown in the following lemma.Lemma 4.1.
(1)(4.1)P(F1)=λ(λ-1)N1(λ),
where N1(λ)=(λ-2)(λ2-3λ+3)(λ3-6λ2+13λ-11) and N1(1)=3.
(2)(4.2)P(F2(a))=(λ-2)P(Ca+1)P(W(5,3))λ(λ-1)=λ(λ-1)(λ-2)2(λ2-4λ+5)Qa+1(λ)=λ(λ-1)N2(λ),
where N2(λ)=(λ-2)2(λ2-4λ+5)Qa+1(λ) and N2(1)=(-1)2(1-4+5)(-1)a+1=2(-1)a+1.
(3)(4.3)P(F3)=λ(λ-1)N3(λ),
where N3(λ)=(λ-2)2(λ2-4λ+5)(λ2-3λ+3) and N3(1)=2.
(4)(4.4)P(F4)=λ(λ-1)N4(λ),
where N4(λ)=(λ-2)3(λ2-3λ+3)2 and N4(1)=-1.
(5)(4.5)P(F5)=λ(λ-1)N5(λ),
where N5(λ)=(λ-2)3(λ3-5λ2+10λ-7) and N5(1)=1.
(6)(4.6)P(F6)=λ(λ-1)N6(λ),
where N6(λ)=(λ-2)(λ2-4λ+5)(λ3-5λ2+9λ-7) and N6(1)=4.
(7)(4.7)P(F7)=λ(λ-1)N7(λ),
where N7(λ)=(λ-2)2(λ3-6λ2+14λ-13) and N7(1)=(-1)2(1-6+14-13)=-4.
(8)(4.8)P(F8(b))=(λ-2)3P(Cb+2)-(λ-3)P(W(b+3,3))=(λ-2)3P(Cb+2)-(λ-2)(λ-3)[P(Cb+2)-P(Cb+1)]=λ(λ-1)(λ-2)[(λ2-5λ+7)Qb+2(λ)+(λ-3)Qb+1(λ)]=λ(λ-1)N8(λ),
where N8(λ)=(λ-2)[(λ2-5λ+7)Qb+2(λ)+(λ-3)Qb+1(λ)] and N8(1)=(-1)[3(-1)b+2+(-2)(-1)b+1]=5(-1)b+1.
(9)(4.9)P(F9)=λ(λ-1)N9(λ),
where N9(λ)=(λ-2)2(λ3-6λ2+14λ-14) and N9(1)=-5.
(10)(4.10)P(F10)=λ(λ-1)N10(λ),
where N10(λ)=(λ-2)(λ4-8λ3+26λ2-41λ+27) and N10(1)=-5.
(11)(4.11)P(F11)=λ(λ-1)N11(λ),
where N11(λ)=(λ-2)2(λ4-7λ3+20λ2-28λ+17) and N11(1)=3.
(12)(4.12)P(F12)=λ(λ-1)N12(λ),
where N12(λ)=(λ-2)3(λ2-4λ+6) and N12(1)=-3.
(13)(4.13)P(F13(c))=(λ-2)[(λ-2)2P(Cc+2)-P(K4)P(Cc+1)λ(λ-1)]=(λ-2)3P(Cc+2)-(λ-2)2(λ-3)P(Cc+1)=λ(λ-1)(λ-2)2[(λ-2)Qc+2(λ)-(λ-3)Qc+1(λ)]=λ(λ-1)N13(λ),
where N13(λ)=(λ-2)2[(λ-2)Qc+2(λ)-(λ-3)Qc+1(λ)] and N13(1)=(-1)2[(-1)(-1)c+2-(-2)(-1)c+1]=3(-1)c+1.
(14)(4.14)P(F14)=λ(λ-1)N14(λ),
where N14(λ)=(λ-2)4(λ2-3λ+4) and N14(1)=2.
(15)(4.15)P(F15(d))=(λ-2)P(W(d+4,3))-(λ-3)P(W(d+3,3))=(λ-2)2[P(Cd+3)-P(Cd+2)]-(λ-2)(λ-3)[P(Cd+2)-P(Cd+1)]=λ(λ-1)(λ-2)[(λ-2)Qd+3(λ)-(2λ-5)Qd+2(λ)+(λ-3)Qd+1(λ)]=λ(λ-1)N15(λ),
where N15(λ)=(λ-2)[(λ-2)Qd+3(λ)-(2λ-5)Qd+2(λ)+(λ-3)Qd+1(λ)] and N15(1)=(-1)[(-1)(-1)d+3-(-3)(-1)d+2+(-2)(-1)d+1]=6(-1)d+1.
(16)(4.16)P(F16)=λ(λ-1)N16(λ),
where N16(λ)=(λ-2)(λ3-7λ2+19λ-19) and N16(1)=6.
(17)(4.17)P(F17)=λ(λ-1)N17(λ),
where N17(λ)=(λ-2)(λ4-8λ3+26λ2-41λ+25) and N17(1)=-3.
(18)(4.18)P(F18(e))=(λ-2)[(λ-1)P(W(e+3,3))-(λ-2)(λ-3)P(Ce+1)]=(λ-1)(λ-2)2[P(Ce+2)-P(Ce+1)]-(λ-2)2(λ-3)P(Ce+1)=(λ-1)(λ-2)2P(Ce+2)-2(λ-2)3P(Ce+1)=λ(λ-1)(λ-2)2[(λ-1)Qe+2(λ)-2(λ-2)Qe+1(λ)]=λ(λ-1)N18(λ),
where N18(λ)=(λ-2)2[(λ-1)Qe+2(λ)-2(λ-2)Qe+1(λ)] and N18(1)=(-1)2[0-2(-1)(-1)e+1]=2(-1)e+1.
(19)(4.19)P(F19)=λ(λ-1)N19(λ),
where N19(λ)=(λ-2)2(λ3-6λ2+14λ-11) and N19(1)=-2.
(20)(4.20)P(F20(f))=P(Wf+1(5,3))-P(W(5,3))P(Cf+1)λ(λ-1)=(λ-2)P(θf+1,2,2)-(λ-2)2P(Cf+2)-(λ-2)(λ2-4λ+5)P(Cf+1)=λ(λ-1)[(λ-2)Mf+1,2,2(λ)-(λ-2)2Qf+2(λ)-(λ-2)(λ2-4λ+5)Qf+1(λ)]=λ(λ-1)N20(λ),
where N20(λ)=(λ-2)Mf+1,2,2(λ)-(λ-2)2Qf+2(λ)-(λ-2)(λ2-4λ+5)Qf+1(λ) and N20(1)=(-1)(-1)f-(-1)f-(-1)(2)(-1)f+1=4(-1)f+1.
(21)(4.21)P(F21)=λ(λ-1)N21(λ),
where N21(λ)=(λ-2)2(λ3-6λ2+14λ-13) and N21(1)=-4.
(22)(4.22)P(F22(h))=P(W(h+3,3))P(W(5,3))P(K3)=(λ-2)(λ2-4λ+5)[P(Ch+2)-P(Ch+1)]=λ(λ-1)(λ-2)(λ2-4λ+5)[Qh+2(λ)-Qh+1(λ)]=λ(λ-1)N22(λ),
where N22(λ)=(λ-2)(λ2-4λ+5)[P(Qh+2(λ)-P(Qh+1(λ)] and N22(1)=(-1)(2)[(-1)h+2-(-1)h+1]=4(-1)h+1.
(23)(4.23)P(F23)=λ(λ-1)N23(λ),
where N23(λ)=(λ-2)(λ2-4λ+5)2 and N23(1)=-4.
(24)(4.24)P(F24)=λ(λ-1)N24(λ),
where N24(λ)=(λ-2)2(λ4-7λ3+20λ2-28λ+17) and N24(1)=3.
(25)(4.25)P(F25)=λ(λ-1)N25(λ),
where N25(λ)=(λ-2)(λ2-4λ+5)(λ3-5λ2+9λ-7) and N25(1)=4.
(26)(4.26)P(F26(j))=P(Wj+1(5,3))-P(W(5,3))P(Cj+1)λ(λ-1)=(λ-2)P(θj+1,2,2)-(λ-2)2P(Cj+2)-(λ-2)(λ2-4λ+5)P(Cj+1)=λ(λ-1)[(λ-2)Mj+1,2,2(λ)-(λ-2)2Qj+2(λ)-(λ-2)(λ2-4λ+5)Qj+1(λ)]=λ(λ-1)N26(λ),
where N26(λ)=(λ-2)Mj+1,2,2(λ)-(λ-2)2Qj+2(λ)-(λ-2)(λ2-4λ+5)Qj+1(λ) and N26(1)=(-1)(-1)j-(-1)j-(-1)(2)(-1)j+1=4(-1)j+1.
(27)(4.27)P(F27)=λ(λ-1)N27(λ)
where N27(λ)=(λ-2)2(λ3-6λ2+14λ-13) and N27(1)=-4.
(28)(4.28)P(F28(k))=(λ-2)3P(Ck+2)-(λ-3)P(W(k+3,3))=(λ-2)3P(Ck+2)-(λ-2)(λ-3)[P(Ck+2)-P(Ck+1)]=λ(λ-1)(λ-2)[(λ2-5λ+7)Qk+2(λ)+(λ-3)Qk+1(λ)]=λ(λ-1)N28(λ),
where N28(λ)=(λ-2)[(λ2-5λ+7)Qk+2(λ)+(λ-3)Qk+1(λ)] and N28(1)=(-1)[3(-1)k+2+(-2)(-1)k+1]=5(-1)k+1.
(29)(4.29)P(F29)=λ(λ-1)N29(λ),
where N29(λ)=(λ-2)(λ4-8λ3+26λ2-41λ+27) and N29(1)=-5.
(30)(4.30)P(F30)=λ(λ-1)N30(λ),
where N30(λ)=(λ-2)(λ4-8λ3+26λ2-42λ+29) and N30(1)=-6.
(31)(4.31)P(F31)=λ(λ-1)N31(λ),
where N31(λ)=(λ-2)2(λ3-6λ2+14λ-13) and N31(1)=-4.Lemma 4.2.
Letℱ1={F4,F5},ℱ2={F2,F3,F14,F18,F19},  ℱ3={F1,F11,F12,F13,F17,F24},  ℱ4={F6,F7,F20,F21,F22,F23,F25, F26,F27,F31},  ℱ5={F8,F9,F10,F28,F29}, and  ℱ6={F15,F16,F30}. Then, for each  F∈ℱi,  i=1,2,3,4,5,6,  H~F implies that  H must be of type  F or  F′ for an  F′ in  ℱi.Proof.
It follows directly from Lemma4.1 that if i≠j, Fp∈ℱi and Fq∈ℱj, then |Np(1)|=i≠j=|Nq(1)|.From Lemmas2.3 and 4.1, we also get the following lemma directly.Lemma 4.3.
(1)F6~F25.
(2)F7~F21~F27~F31.
(3)F8(b)~F28(k) if and only if b=k.
(4)F10~F29.
(5)F11~F24.
(6)F20(f)~F26(j) if and only if f=j.


## 5. Proof of the Main Theorem

We are now ready to prove our main theorem.(1) LetH~F1. By Lemma 4.2, H is of type (1), (11), (12), (13), (17), or (24). If H=F1, then H is of type F1. Lemma 4.1 further implies that P(F1,λ)≠P(Fi,λ), i=11,12,17,24. Hence, H cannot be of type (11), (12), (17), or (24). If H=F13(c), by Lemma 2.3, c=3. Using Software Maple, we have (5.1)P(F13(3))=λ(λ-1)(λ-2)2(λ4-7λ3+20λ2-28λ+17)≠(λ-2)(λ2-3λ+3)(λ3-6λ2+13λ-11)=P(F1).
Thus, H must be of type F1.(2) LetH~F2. By Lemma 4.2, H is of type (2), (3), (14), (18), or (19). If H=F2(a′), then by Lemma 2.3, a′=a. Thus, H must be of type F2. Since F2(a) has two induced C4s while each of F3 and F19 has at least three induced C4s, by Lemma 2.3, H cannot be of type (3) or (19). Since P(F14) is divisible by (λ-2)4 but not P(F2(a)), H cannot be of type (14). If H=F18(e), then by Lemma 2.3, e=a. Note that (5.2)P(F2(a))=(λ-1)(λ-2)3P(Ca+1)-(λ-2)2(λ-3)P(Ca+1),P(F18(a))=(λ-1)(λ-2)P(W(a+3,3))-(λ-2)2(λ-3)P(Ca+1).
This implies that (λ-2)2P(Ca+1)=P(W(a+3,3)), a contradiction since P(W(a+3,3)) is not divisible by (λ-2)2. Thus, H∈〈F2(a)〉 if and only if H is of type F2(a).(3) LetH~F3. By Lemma 4.2 and the above result, H is of type (3), (14), (18), or (19). If H=F3, then H is of type F3. By Lemma 4.1, F3≁F14 and F19. If H=F18(e), by Lemma 2.3, e=3. Using Software Maple, we have (5.3)P(F18(3),λ)=λ(λ-1)(λ-2)4(λ2-3λ+4)≠(λ-2)2(λ2-4λ+5)(λ2-3λ+3)=P(F3,λ).
Thus, H must be of type F3.(4) LetH~F4. By Lemma 4.2, H is of type (4) or (5). If follows directly from Lemma 4.1 that F4≁F5. Thus, H must be of type F4.(5) LetH~F5. By Lemma 4.2 and the above result, H must be of type (5). Thus, H must be of type F5.(6) By Lemma4.2, H is of type (6), (7), (20), (21), (22), (23), (25), (26), (27), or (31). If H=F6, then H≅F6. Note that Lemma 4.1 implies that F6≁Fi, i=7,21,23,27,31. If H=F20(f), F22(h), or F26(j), by Lemma 2.3, f=h=j=3. Using Software Maple, we have (5.4)P(F20(3),λ)=P(F26(3),λ)=λ(λ-1)(λ-2)2(λ4-7λ3+20λ2-28λ+18)≠λ(λ-1)(λ-2)(λ2-4λ+5)(λ3-5λ2+9λ-7)=P(F22(3),λ)=P(F6,λ).
Thus, by Lemma 4.3, H∈〈F6〉 if and only if H≅F6,F25 or of type F22(3).(7) LetH~F7. By Lemma 4.2 and the above results, H is of type (7), (20), (21), (22) where h≥4, (23), (26), (27), or (31). If H=Fi, i=7,21,27,31, Lemma 4.3 implies that H≅F7, F21, F27, or H is of type F31. Lemma 4.1 further implies that H cannot be of type (20), (22), (23), or (26). Thus, H∈〈F7〉 if and only if H≅F7, F21, F27, or H is of type F31.(8) LetH~F8(b). By Lemma 4.2, H is of type (8), (9), (10), (28), or (29). If H=F8(b′), by Lemma 2.3, b′=b. Thus, H≅F8(b). Since F8(b) is of order at least 8 but Fi, i=9,10,29 is of order 7, by Lemma 2.3, P(F8(b))≠P(Fi), i=9,10,29. By Lemma 4.3, P(F8(b))=P(F28(b)). Hence, 〈F8(b)〉={F8(b),F28(b)}.(9) LetH~F9. By Lemma 4.2 and the above results, H is of type (9), (10), or (29). By Lemma 4.1, F9≁F10,F29. Thus, H≅F9 and F9 is χ-unique.(10) LetH~F10. By Lemma 4.2 and the above result, H is of type (10) or (29). By Lemma 4.3, 〈F10〉={F10,F29}.(11) LetH~F11. By Lemma 4.2 and the above result, H is of type (11), (12), (13), (17), or (24). If H=F11 or F24, by Lemma 4.3, H must be of type F11 or F24. Lemma 4.1 further implies that P(F11,λ)≠P(F12,λ) and P(F17,λ). Hence, H cannot be of type (12) or (17). If H=F13(c), Lemma 2.3 implies that c=3. Using Software Maple, we have (5.5)P(F13(3),λ)=λ(λ-1)(λ-2)2(λ4-7λ3+20λ2-28λ+17)=P(F11,λ).
Hence, H∈〈F11〉 if and only if H is of type F11, F13(3), or F24.(12) LetH~F12. By Lemma 4.2 and the above result, H is of type (12), (13) with c≥4 or (17). Since F12 and F13(c) have different order, Lemma 2.3 implies that F12≁F13. Lemma 4.1 also implies that F12≁F17. Thus, H must be of type F12.(13) LetH~F13(c),c≥4. By Lemma 4.2 and the above result, H is of type (13) with c≥4 or (17). If H=F13(c′), then c′=c. Since F13(c) and F17 have different order, Lemma 2.3 implies that F13(c)≁F17. Thus, H∈〈F13(c)〉 if and only if H is of type F13(c) for c≥4 and H∈〈F13(3)〉 if and only if H is of type F11, F13(3), or F24.(14) LetH~F14. By Lemma 4.2 and the above result, H is of type (14), (18) or (19). If H=F14, then H is of type F14. If H=F18(e), by Lemma 2.3, e=3. Using Software Maple, we have (5.6)P(F18(3),λ)=λ(λ-1)(λ-2)4(λ2-3λ+4)=P(F14,λ).
By Lemma 4.1, we also have F14≁F19. Hence, H∈〈F14〉 if and only if H is of type F14 or F18(3).(15) LetH~F15(d). By Lemma 4.2, H must be of type (15), (16), or (30). If H=F15(d′), by Lemma 2.3, d′=d. Thus, H≅F15. Since F16 has exactly six induced C4s while F15(d) has only two induced C4s, by Lemma 2.3, H cannot be of type (16). If H=F31, by Lemma 2.3, d=2. Using Software Maple, we have (5.7)P(F15(2))=λ(λ-1)(λ-2)(λ4-8λ3+26λ2-42λ+29)=P(F30).
Thus, 〈F15(2)〉={F15(2),F30} and F15(d) is χ-unique for d≥3.(16) LetH~F16. By Lemma 4.2 and the above results, H≅F16. Thus, F16 is χ-unique.(17) LetH~F17. By Lemma 4.2 and the above results, H≅F17. Thus, F17 is χ-unique.(18) LetH~F18(e), e≥4. By Lemma 4.2 and the above results, H must be of of type (18) with e≥4, or (19). If H=F18(e′), Lemma 2.3 implies that e′=e. Since F18(e) and F19 are of different order, it follows that H cannot be of type (19). Thus, H∈〈F18(e)〉 if and only if H is of type F18(e) for e≥4, and H∈〈F18(3)〉 if and only if H is of type F14 or F18(3).(19) LetH~F19. By Lemma 4.2 and the above results, H must be of type F19.(20) LetH~F20(f). By Lemma 4.2 and the above results, H must be of type (20), (22) where h≥4, (23) or (26). If H=F20(f′), Lemma 2.3 implies that f′=f. If H=F22(h), Lemma 2.3 implies that h=f. Note that (5.8)P(F20(f))=(λ-1)P(W(f+4,4))-(λ-3)P(W(f+3,3)),P(F22(f))=(λ-1)(λ-2)P(W(f+3,3))-(λ-3)P(W(f+3,3)).
This implies that P(W(f+4,4))=(λ-2)P(W(f+3,3)), a contradiction since P(W(f+4,4)) is not divisible by (λ-2)2 but (λ-2)P(W(f+3,3)) is divisible by (λ-2)2. Since F20 and F23 are of different order, Lemma 2.3 further implies that H cannot be of type (23). Lemma 4.3 then implies that 〈F20(f)〉={F20(f),F26(f)}.(21) The result follows directly from (7) above.(22) LetH~F22(h), h≥4. By Lemma 4.2 and the above result, H is of type (22) with h≥4, or (23). If H=F22(h′), Lemma 2.3 implies that h′=h. Since F22(h) and F23 are of different order, Lemma 2.3 further implies that H cannot be of type (23). Thus, H∈〈F22(h)〉 if and only if H is of type F22(h) for h≥4, and H∈〈F22(3)〉 if and only if H≅F6, F25 or H is of type F22(3).(23) LetH~F23. By Lemma 4.2 and the above results, H must be of type F23. Thus, H∈〈F23〉 if and only if H is of type F23.(24) The result follows directly from (11) above.(25) The result follows directly from (6) above.(26) The result follows directly from (20) above.(27) The result follows directly from (7) above.(28) The result follows directly from (8) above.(29) The result follows directly from (10) above.(30) The result follows directly from (15) above.(31) The result follows directly from (7) above.This completes the proof of our main theorem.


## 6. Further Research

The above results and the main results in [6, 7] completely determined the chromaticity of all 2-connected (n,n+4)-graphs with (i) exactly 3 triangles (and at least one induced 4-cycle) and (ii) at least 4 triangles. However, the study of the chromaticity of 2-connected (n,n+4)-graphs with exactly 3 triangles is far from completion although all 23 χr-closed families of such graphs have been obtained in [8] as shown in Figure 2. Base on the above results, it is expected that many different families of 2-connected (n,n+4)-graphs with exactly 3 triangles are χ-equivalent. Perhaps, the approach used in the study of the chromaticity of K4-homeomorphs (see [13]) or a more efficient approach of comparing the chromatic polynomials of graphs can be applied in solving the following problem.Figure 2
Relative-closed family of 2-connected(n,n+4)-graphs with exactly 3 triangles. The light lines of the graphs refer to the paths with edges not belong to any triangles.Problem 1.
Determine the chromatic uniqueness of all 2-connected(n,n+4)-graphs with exactly 3 triangles.



---

*Source: 430396-2011-11-02.xml*