PDF

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

THE CHROMATIC EQUIVALENCE CLASS OF GRAPH `(B_n−6,1,2)

Jianfeng Wang^1,2, Qiongxiang Huang², Chengfu Ye¹  and  Ruying Liu¹

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

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

Abstract

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 `(B<sub>n−7,1,3</sub>), 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 `(B_n−6,1,2) that is the complement of B_n−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.

References

[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