Font Size: a A A

On The Chromatic Uniqueness Of Tripartite Graphs K(m,n,r)-A(|A|=2)

Posted on:2005-06-30Degree:MasterType:Thesis
Country:ChinaCandidate:F Q LiFull Text:PDF
GTID:2120360125452853Subject:Basic mathematics
Abstract/Summary:PDF Full Text Request
Let G be a simple graph and let P(G, A) denote the chromatic polynomial of G. A graph G is said to be chromatically unique if for any graph H , P(H, A) = P(G, A) implies that H is isomorphic to G. Let K(m,n,r) denote the complete tripartite graph. In this paper we prove that1). If 3 m n r, let s = , if m + n +r > 2 s + 3s2, graphs K(m,n,r) - A(| A |= 2) are chromatically unique;2). If m 4, graphs K(m, m, m) - A, K(m, m, m + 1) - A, K(m, m + 1, m + 1) - A, (| A |= 2 ) are all chromatically unique;3). Let n, k be non-negative integers, if n > +2, K(n-k,n,n) - A;k, n, n + k) - A (| A |= 2) are all chromatically unique graphs.
Keywords/Search Tags:tripartite graph, chromatic polynomial, chromatically unique, partition into colour classes
PDF Full Text Request
Related items