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

Abstract

For m ≥ 3, let ℱm be the family of graphs G that possesses an independent set partition {A1 , . . . , Am} such that the subgraphs of G induced by Ai ∪ Aj are trees except one, which is a forest having two components. Let t(G) denote the number of triangles in G. It is shown that for each G of order n in ℱm, (formula presented) Let (formula presented) In this paper, we characterize (1) the graphs in ℱm 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 λ(λ - 1) ⋯ (λ - m + 3)(λ - m + 2)2(λ - m + 1)n-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).