Generalized Tree Structure And Color

This paper is about the search for the chromatic polynomials and chromaticuniqueness of generalized trees (or g.trees )which is a new topic on chromaticityof graphs after the search for chromaticity of q-trees, generalized θ-graphs andgeneralized wheel graphs θ_n,k. A graph is chordal if it does not contains chordlesscycles on more than three vertices as an induced subgraph, chordal graphs havesimilar chromatic polynomials as follows:P(G,λ) = λ^r₀(λ-1)^r₁ ···(λ-m)^r_m,where r₁ + r₂ + ···+ r_m = |v(G)|, r_i ∈Z⁺(i = 1,2,···,m). In 1974, K. Brownput up the conjecture that a graph is chordal if its chromatic polynomial onlyhas non-negative integral roots. Nevertheless, R.C. Reed rejected the conjectureby creating a non-chordal graph H₇ successfully in 1975, which was obtained byadding one new vertex to any edge of K₆, although H₇ has chromatic polyno-mial P(H₇,λ) as follows: P(H₇,λ) = λ(λ-1)(λ-2)(λ-3)³(λ-4), but thereare four chordless 4-cycles in H₇. So H₇ isn't a chordal graph. In other words,chordal graphs are not determined by their chromatic polynomials. A g.tree is aconnected chordal graph. In turn to the characterizations of chromatic classi?-cation, critical graphs, chromatic equivalence, this paper gives several classes ofg.trees determined by their chromatic polynomials. Furthermore, this paper indi-rectly give a complete solution to the K. Brown conjecture and meantime obtaina suficient and necessary condition for the chromatic uniqueness of g.trees.This paper includes ?ve chapters. In the first chapter, a preface introducesthe background of the search for the chromaticity of graphs and author's mainworks in this thesis. and chapter two shows the necessary foundmental the-orems and results on the chromatic polynomials, chromatic equivalence, chro-matic uniqueness. In chapter three, g.trees and non-g.trees are introduced anddiscussed. In addition, this chapter give several classes of g.trees determined bytheir chromatic polynomials. As a conclusion, the forth chapter does researchin the chromatic polynomials of g.trees and provide a sufficient and necessarycondition for the chromatic uniqueness of g.trees. Which is, A g.tree is χ-unique...