科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let Ft (n) denote the family of all connected graphs of ordern with clique number t. In this paper, we present a new upper bound for the chromatic polynomial of a graph G in Ft (n) in terms of the clique number of G. Moreover, we also show that the conjecture proposed by Tomescu, which says that if x =k = 4 and G is a connected graph on n vertices with chromatic number k, thenP(G, x) = (x)k(x - 1)(n-k) holds under certain conditions, where (x)(k) = x(x - 1) . . . (x - k + 1), such as the clique number ? (G) = k = 4, ? (G) = k -1 (k = 7) with two (k - 1)-cliques having at most k - 3 vertices in common, or maximum degree ?(G) = n - 2.
