On graphs in which any pair of colour classes but one induces a tree

✍ Scribed by F.M. Dong; K.M. Koh

• Book ID: 103062410
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 659 KB
• Volume: 169
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00331-p

✦ Synopsis

For m >~ 3, let .~,, be the family of graphs G that possesses an independent set partition {AI ..... Am} such that the subgraphs of G induced by Ai U Aj are trees except one, which is a tbrest having two components. Let t(G) denote the number of triangles in G. It is shown that

In this paper, we characterize (1) the graphs in ,7,, with p(G) -0 and (2) the graphs in ~3 with p(G) = 1. By applying the first characterization, we deduce that a graph G of order n>>,m is in ,~-m with p(G) = 0 iff its chromatic polynomial is given by 2(2 -1).-.

(2 -m + 3)(2 -m + 2)2(2 -m + 1 ),-m By applying the second characterization, we (i) classify some of the graphs G in ~3 with p(G) = 1 via their chromatic polynomials and (ii) show that the graphs obtained from the wheels of even order by deleting two consecutive spokes are uniquely determined by their chromatic polynomials, which solves partially Problem 4 in Koh and Teo (1990).