×

zbMATH — the first resource for mathematics

A new family of chromatically unique 6-bridge graph. (English) Zbl 1443.05069
Summary: For a graph \(G\), let \(P(G, \lambda)\) denote the chromatic polynomial of \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent (or simply \(\chi\)-equivalent), denoted by \(G \sim H\), if \(P(G, \lambda)=P(H, \lambda)\). A graph \(G\) is chromatically unique (or simply \(\chi\)-unique) if for any graph \(H\) such as \(H \sim G\), we have \(H \cong G\), i.e, \(H\) is isomorphic to \(G\). In this paper, the chromatic uniqueness of a new family of 6-bridge graph \(\theta (a,a,b,b,b,c)\) where \(2 \leq a \leq b \leq c\), is investigated.
MSC:
05C15 Coloring of graphs and hypergraphs
05C31 Graph polynomials
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] X. W. Bao and X. E. Chen, Chromaticity of the graph θ(a,b,c,d,e) (in Chinese), J. Xinjiang Univ. Natur. Sci. 11, pp. 19-22, (1994). · Zbl 0964.05511
[2] C. Y. Chao and E. G. Whitehead Jr. , On chromatic equivalence of graphs, Theory and Applications of Graphs, Lecture Notes in Math. 642, Springer, Berlin, pp. 121-131, (1978).
[3] X. E. Chen, X. W. Bao and K. Z. Ouyang, Chromaticity of the graph θ(a,b,c,d), J. Shaanxi Normal Univ. 20, pp. 75-79, (1992).
[4] F. M. Dong, K. M. Koh and K. L. Teo, Chromatic polynomials and chromaticity of graphs, World Scientific Publishing Ptd. Ltd., Singapore, pp. 105-123, (2005). · Zbl 1070.05038
[5] F. M. Dong, K. L. Teo, C. H. C. Little, M. Hendy and K. M. Koh, Chromatically unique multibridge graphs, The Electric Journal of Combinatorics 11(2004) #R12. · Zbl 1031.05047
[6] F. Harary, Graph theory, Addison-Wesley Publishing Company Inc., United States of America, (1972). · Zbl 0235.05105
[7] N. S. A. Karim, R. Hasni and G.C. Lau, Chromatic uniqueness of 6-bridge graph θ(a,a,a,b,b,c), Electronic Journal of Graph Theory and Applications 4(1), pp. 60-78, (2016).
[8] N. S. A. Karim, Chromaticity of K_4-homeomorphs with girth 9 and 6-bridge graph, Doctoral Dissertation, Universiti Malaysia Terengganu, Terengganu, Malaysia, (2015).
[9] A. M. Khalaf, Chromaticity of a certain k-bridge graphs, Doctoral Dissertation, Universiti Putra Malaysia, Serdang, Malaysia, (2010).
[10] A. M. Khalaf and Y. H. Peng, Another proof of a family of chromatically unique 5-bridge graphs, International Journal of Applied Mathematics 22(6), pp. 1009-1020, (2009). · Zbl 1179.05046
[11] A. M. Khalaf and Y. H. Peng, A note on chromaticity of k-bridge graphs, Far East J. Math. Sci. 34(3), pp. 353-359, (2009). · Zbl 1209.05089
[12] A. M. Khalaf and Y. H. Peng, The chromatic uniqueness of a family of 6-bridge graphs, AKCE J. Graphs Combin. 6(3), pp. 393-400, (2009). · Zbl 1210.05042
[13] A. M. Khalaf and Y. H. Peng, Chromaticity of the 6-bridge graph θ(a,a,a,b,c,c), International Journal of Applied Mathematics 22(7), pp. 1087-1111, (2009). · Zbl 1200.05083
[14] A. M. Khalaf and Y. H. Peng, A family of chromatically unique 6-bridge graphs, Ars Combin. 94, pp. 211-220, (2010). · Zbl 1240.05088
[15] A. M. Khalaf, Y. H. Peng and K. A. Atan, Chromaticity of 5-bridge graphs (II), International Journal of Applied Mathematics 23, pp. 791-808, (2010). · Zbl 1282.05042
[16] K. M. Koh and K. L. Teo, The search for chromatically unique graphs, Graphs Combin. 6, pp. 259-285, (1990). · Zbl 0727.05023
[17] K. M. Koh and K. L. Teo, The search for chromatically unique graphs-II, Discrete Math. 172, pp. 59-78, (1997). · Zbl 0879.05031
[18] X. F. Li, A family of chromatically unique 5-bridge graphs, Ars Combin. 88, pp. 415-428, (2008). · Zbl 1224.05243
[19] X. F. Li and X. S. Wei, The chromatic uniqueness of a family of 5-bridge graphs (in Chinese), J. Qinghai Normal Univ. 2, pp. 12-17, (2001).
[20] B. Loerinc, Note: Chromatic uniqueness of the generalized θ-graph, Discrete Math. 23, pp. 313-316, (1978). · Zbl 0389.05034
[21] D. B. West, Introduction to graph theory 2nd ed., Prentice Hall, Inc., United States of America, (2001).
[22] S. Xu, J. Liu and Y. H. Peng, The chromaticity of s-bridge graphs and related graphs, Discrete Math. 135, pp 349-358, (1994). · Zbl 0814.05036
[23] C. F. Ye, The chromatic uniqueness of 6-bridge graphs (in Chinese), J. Math. Study 34(4), pp. 399-421, (2001). · Zbl 0996.05057
[24] C. F. Ye, The chromatic uniqueness of s-bridge graphs (in Chinese), J. Xinjiang Univ. Natur. Sci. 19(3), pp. 246-265, (2002).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.