On the structure and chromaticity of graphs in which any two colour classes induce a tree

Abstract

For r≥2, let script T signr be the family of graphs G which possesses an independent set partition {A1,...,Ar} such that the subgraph induced by Ai ∪ Aj in G is a tree for all i and j with 1 ≤i < j ≤r. Let v(G) and t(G) denote, respectively, the order of G and the number of triangles in G. Define t(r, n) = max{t(G) \ G ∈ script T signr, v(G) = n}. It is known that the family {G \ G ∈ script T signr, t(G) = t(r, n)} is the family of (r - 1)-trees of order n, and the family of r-trees of the same order forms a chromatically equivalence class. In this paper, we determine the structure of the graphs in the family {G \ G ∈ script T signr, t(G) = t(r, n) - 1} and apply the structural results to investigate the chromaticity of the graphs of the family. A number of new families of chromatically unique graphs are discovered.