The chromaticity of wheels
โ Scribed by Shao-Ji Xu; Nian-Zu Li
- Publisher
- Elsevier Science
- Year
- 1984
- Tongue
- English
- Weight
- 746 KB
- Volume
- 51
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
โฆ Synopsis
In this paper we prove that the wheel W,, show tha*: W, is not chromatically unique.
+1 is chromatically unique ifnis even. We also Two graphs G and H are said to be chromatically equivalent 2 they ha?re the same chromlatic polynomial, i.e.
, P(G, A)==P(H, A). A graph G is said to be chromatically unique, if P(& A) = P(G, A
) implies that H is isomorphic to G. In [l J, the question was raised as to whether or not the wheels, Wn+l for n 3 4, are chromatically unique. In C;!], it was shown that WS is chromatically unique and Wt, is not chromatically unique. In this paper, we prove that xNn+l is chromaticallg~ unique, if n 24 and n is e ven. (In this paper we always suppose n 3 4.) Vue also show that W.. is not chron~atically unique.
IASDBUB L Let T be a tree with n oertices, q) be a uertex whkh is adjacent to euery uetiex of T, i.e. , d(u) = n, andH denote the join T + u. 'I*hen trbere are n -1 tnangles in 1% bOf. By irlductim on n, we obtain the conclusion immediately. 0 By using Lemma 1 we can obtain the following two lemmas. knm~l 2 Lef T 1% a tree with n uertices, u be a uertex which is adjacmt to m ue@ces of Y', i.e., d(u) = m G n, and N denote this graph. Then thle number of *'&is work 'IHas done while the author was a visiting scholar at the University of Pittsbu*gh.
๐ SIMILAR VOLUMES
In the previous paper, it was shown that the graph U. รท 1 obtained from the wheel W n รท 1 by deleting a spoke is uniquely determined by its chromatic polynomial if n >i 3 is odd. In this paper, we show that the result is also true for even n >~ 4 except when n = 6 in which case, the graph W given in
We prove that the chromatic Ramsey number of every odd wheel W 2k+1 , k โฅ 2 is 14. That is, for every odd wheel W 2k+1 , there exists a 14-chromatic graph F such that when the edges of F are two-coloured, there is a monochromatic copy of W 2k+1 in F, and no graph F with chromatic number 13 has the s
A graph G is called triangulated (or rigid-circuit graph, or chordal graph) if every circuit of G with length greater than 3 has a chord. It can be shown (see, UI, . . . , u,, . Let G = G,.