کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650206 1342479 2009 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Chromatic equivalence classes of complete tripartite graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Chromatic equivalence classes of complete tripartite graphs
چکیده انگلیسی

Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph Km,n,rKm,n,r are developed. Using these, we obtain the chromatic equivalence classes for Km,n,nKm,n,n (where 1≤m≤n1≤m≤n) and Km1,m2,m3Km1,m2,m3 (where |mi−mj|≤3|mi−mj|≤3). In particular, it is shown that (i) Km,n,nKm,n,n (where 2≤m≤n2≤m≤n) and (ii) Km1,m2,m3Km1,m2,m3 (where |mi−mj|≤3|mi−mj|≤3, 2≤mi,i=1,2,32≤mi,i=1,2,3) are uniquely determined by their chromatic polynomials. The result (i), proved earlier by Liu et al. [R.Y. Liu, H.X. Zhao, C.Y. Ye, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math. 289 (2004) 175–179], answers a conjecture (raised in [G.L. Chia, B.H. Goh, K.M. Koh, The chromaticity of some families of complete tripartite graphs (In Honour of Prof. Roberto W. Frucht), Sci. Ser. A (1988) 27–37 (special issue)]) in the affirmative, while result (ii) extends a result of Zou [H.W. Zou, On the chromatic uniqueness of complete tripartite graphs Kn1,n2,n3Kn1,n2,n3 J. Systems Sci. Math. Sci. 20 (2000) 181–186].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 1, 6 January 2009, Pages 134–143
نویسندگان
, ,