The chromatic equivalence class of graph $\overline{B_{n-6,1,2}}$

Jianfeng Wang ; Qiongxiang Huang ; Chengfu Ye ; Ruying Liu

Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 189-218 / Harvested from The Polish Digital Mathematics Library

Résumé

By h(G,x) and P(G,λ) we denote the adjoint polynomial and the chromatic polynomial of graph G, respectively. A new invariant of graph G, which is the fourth character R₄(G), is given in this paper. Using the properties of the adjoint polynomials, the adjoint equivalence class of graph $B_{n-6,1,2}$ is determined, which can be regarded as the continuance of the paper written by Wang et al. [J. Wang, R. Liu, C. Ye and Q. Huang, A complete solution to the chromatic equivalence class of graph $\overline{B_{n-7,1,3}}$, Discrete Math. (2007), doi: 10.1016/j.disc.2007.07.030]. According to the relations between h(G,x) and P(G,λ), we also simultaneously determine the chromatic equivalence class of $\overline{B_{n-6,1,2}}$ that is the complement of $B_{n-6,1,2}$.

Détail

Publié le : 2008-01-01

Zbl 1156.05021

EUDML-ID : urn:eudml:doc:270688

Bibliographie

[000] [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, Amsterdam, 1976). | Zbl 1226.05083

[001] [2] F.M. Dong, K.M. Koh, K.L. Teo, C.H.C. Little and M.D. Hendy, Two invariants for adjointly equivalent graphs, Australasian J. Combin. 25 (2002) 133-143. | Zbl 0993.05067

[002] [3] F.M. Dong, K.L. Teo, C.H.C. Little and M.D. Hendy, Chromaticity of some families of dense graphs, Discrete Math. 258 (2002) 303-321, doi: 10.1016/S0012-365X(02)00355-2. | Zbl 1010.05024

[003] [4] Q.Y. Du, The graph parameter π (G) and the classification of graphs according to it, Acta Sci. Natur. Univ. Neimonggol 26 (1995) 258-262.

[004] [5] B.F. Huo, Relations between three parameters A(G), R(G) and D₂(G) of graph G (in Chinese), J. Qinghai Normal Univ. (Natur. Sci.) 2 (1998) 1-6.

[005] [6] K.M. Koh and K.L. Teo, The search for chromatically unique graphs, Graphs and Combin. 6 (1990) 259-285, doi: 10.1007/BF01787578. | Zbl 0727.05023

[006] [7] K.M. Koh and K.L. Teo, The search for chromatically unique graphs-II, Discrete Math. 172 (1997) 59-78, doi: 10.1016/S0012-365X(96)00269-5. | Zbl 0879.05031

[007] [8] R.Y. Liu, Several results on adjoint polynomials of graphs (in Chinese), J. Qinghai Normal Univ. (Natur. Sci.) 1 (1992) 1-6.

[008] [9] R.Y. Liu, On the irreducible graph (in Chinese), J. Qinghai Normal Univ. (Natur. Sci.) 4 (1993) 29-33.

[009] [10] R.Y. Liu and L.C. Zhao, A new method for proving uniqueness of graphs, Discrete Math. 171 (1997) 169-177, doi: 10.1016/S0012-365X(96)00078-7. | Zbl 0881.05046

[010] [11] R.Y. Liu, Adjoint polynomials and chromatically unique graphs, Discrete Math. 172 (1997) 85-92, doi: 10.1016/S0012-365X(96)00271-3. | Zbl 0878.05030

[011] [12] J.S. Mao, Adjoint uniqueness of two kinds of trees (in Chinese), The thesis for Master Degree (Qinghai Normal University, 2004).

[012] [13] R.C. Read and W.T. Tutte, Chromatic Polynomials, in: L.W. Beineke, R.T. Wilson (Eds), Selected Topics in Graph Theory III (Academiv Press, New York, 1988) 15-42. | Zbl 0667.05022

[013] [14] S.Z. Ren, On the fourth coefficients of adjoint polynomials of some graphs (in Chinese), Pure and Applied Math. 19 (2003) 213-218. | Zbl 1123.05301

[014] [15] J.F. Wang, R.Y. Liu, C.F. Ye and Q.X. Huang, A complete solution to the chromatic equivalence class of graph $\overline{B_{n-7,1,3}}$, Discrete Math. 308 (2008) 3607-3623. | Zbl 1225.05136

[015] [16] C.F. Ye, The roots of adjoint polynomials of the graphs containing triangles, Chin. Quart. J. Math. 19 (2004) 280-285.

[016] [17] H.X. Zhao, Chromaticity and Adjoint Polynomials of Graphs, The thesis for Doctor Degree (University of Twente, 2005). The Netherlands, Wöhrmann Print Service (available at http://purl.org/utwente/50795)