Discussiones Mathematicae Graph Theory 28(2) (2008) 189-218
doi: 10.7151/dmgt.1401

[BIBTex] [PDF] [PS]


Jianfeng Wang1,2, Qiongxiang Huang2, Chengfu Ye1  and  Ruying Liu1

1Department of Mathematics and Information Science
Qinghai Normal University, Xining, Qinghai 810008, P.R. China

2College of Mathematics and System Science
Xinjiang University, Urumqi, Xinjiang 830046, P.R. China
e-mail: jfwang4@yahoo.com.cn


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 R4(G), is given in this paper. Using the properties of the adjoint polynomials, the adjoint equivalence class of graph Bn−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 `(Bn−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 `(Bn−6,1,2) that is the complement of Bn−6,1,2.

Keywords: chromatic equivalence class, adjoint polynomial, the smallest real root, the second smallest real root, the fourth character.

2000 Mathematics Subject Classification: 05C15, 05C60.


[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, Amsterdam, 1976).
[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.
[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.
[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.
[5] B.F. Huo, Relations between three parameters A(G), R(G) and D2(G) of graph G (in Chinese), J. Qinghai Normal Univ. (Natur. Sci.) 2 (1998) 1-6.
[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.
[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.
[8] R.Y. Liu, Several results on adjoint polynomials of graphs (in Chinese), J. Qinghai Normal Univ. (Natur. Sci.) 1 (1992) 1-6.
[9] R.Y. Liu, On the irreducible graph (in Chinese), J. Qinghai Normal Univ. (Natur. Sci.) 4 (1993) 29-33.
[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.
[11] R.Y. Liu, Adjoint polynomials and chromatically unique graphs, Discrete Math. 172 (1997) 85-92, doi: 10.1016/S0012-365X(96)00271-3.
[12] J.S. Mao, Adjoint uniqueness of two kinds of trees (in Chinese), The thesis for Master Degree (Qinghai Normal University, 2004).
[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.
[14] S.Z. Ren, On the fourth coefficients of adjoint polynomials of some graphs (in Chinese), Pure and Applied Math. 19 (2003) 213-218.
[15] J.F. Wang, R.Y. Liu, C.F. Ye and Q.X. Huang, A complete solution to the chromatic equivalence class of graph `(Bn−7,1,3), Discrete Math. 308 (2008) 3607-3623.
[16] C.F. Ye, The roots of adjoint polynomials of the graphs containing triangles, Chin. Quart. J. Math. 19 (2004) 280-285.
[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).

Received 30 November 2006
Revised 26 February 2008
Accepted 28 February 2008