On q-trees

✍ Scribed by Chong-Yun Chao; Nian-Zu Li; Shao-Ji Xu

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 301 KB
• Volume: 10
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190100116

✦ Synopsis

We show that a graph G with n vertices is a q-tree if and only if its chromatic polynomial is P(G,A) = A(A -I)...(A -q + l ) ( As ) " -~

where n L q.

The graphs which we consider here are finite, undirected, simple, and loopless. Let q be an integer L 1. The graphs called q-trees are defined by recursion: the smallest q-tree is the complete graph Kq with q vertices, and a q-tree with n + 1 vertices where n I q is obtained by adding a new vertex adjacent to each of q arbitrarily selected but mutually adjacent vertices of a q-tree with n vertices. In [2], Read characterized 1-trees (trees) by their chromatic polynomials, i.e., a graph G with n vertices is a 1-tree if and only if its chromatic polynomial is P(G, A) = A(A -I)"-'. In [3], Skupien stated the problem of finding analogous characterizations of q-trees for q 2 2. In 141, Whitehead characterized 2-trees, i.e., a graph G with n vertices is a 2-tree if and only if P(G, A) = A(A -1) (A -2)n-2, and he conjectured that a graph G with n vertices is a q-tree if and only if P(G, A) = A(A -1) * * * (A -q + 1) (Aq)"-q where n 2 q I 1. Here, we shall show that the conjecture is true, i.e., we prove the following *This work was done while the author was a visiting scholar at the University of Pittsburgh.