کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649343 | 1342450 | 2009 | 6 صفحه PDF | دانلود رایگان |
Let P(G,λ)P(G,λ) be the chromatic polynomial of a graph GG. A graph GG is chromatically unique if for any graph HH, P(H,λ)=P(G,λ)P(H,λ)=P(G,λ) implies H is isomorphic to GG. For integers k≥0k≥0, t≥2t≥2, denote by K((t−1)×p,p+k)K((t−1)×p,p+k) the complete tt-partite graph that has t−1t−1 partite sets of size pp and one partite set of size p+kp+k. Let K(s,t,p,k)K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k)K((t−1)×p,p+k) by adding a set SS of ss edges to the partite set of size p+kp+k such that 〈S〉〈S〉 is bipartite. If s=1s=1, denote the only graph in K(s,t,p,k)K(s,t,p,k) by K+((t−1)×p,p+k)K+((t−1)×p,p+k). In this paper, we shall prove that for k=0,1k=0,1 and p+k≥s+2p+k≥s+2, each graph G∈K(s,t,p,k)G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K+((t−1)×p,p+k)K+((t−1)×p,p+k) is chromatically unique for k=0,1k=0,1 and p+k≥3p+k≥3.
Journal: Discrete Mathematics - Volume 309, Issue 12, 28 June 2009, Pages 4089–4094