CHROMATICITY OF WHEELS WITH MISSING THREE SPOKES

Abstract

All graph consider here are simple graphs. For a graph G, Let V(G) and E(G) be the vertex set and a edge set of graph G, respectively. The order of G is denoted by v(G), and the size of G by e(G), i.e. v(G)=|V(G)| and e(G) = |E(G)|. Let P(G,λ) (or simply P(G)) denote the chromatic polynomial of graph G. Two graphs G and H are called chromatically equivalent if P(G)=P(H), and G is called chromatically unique if P(G)=P(H) implies H isomorphic to G for any graph H [9]. A wheel W_n is a graph obtained by taking the join of K_1 and the cycle C_(n-1), edges which join K_1 to the vertices of C_(n-1) are called the spokes [2]. Let W_n be wheel of order n and let W(n,k) be the graph obtained from W_n by deleting all but k consecutive spokes, where n≥4 and 1≤k≤ n – 1. Chia [2] showed that W(n,n-2) is chromatically unique for any even integers n≥6. In [1], W(5,3) was proved to be chromatically unique. Dong and Li, [5], proved that for any odd integer n≥9,W(n,n-2) is chromatically unique, and just one graph, ( shown in Fig.1(b)) is chromatically equivalent to W(7,5), and is not isomorphic to it. It is easy to check that W(4,1) and W(5,2) are chromatically unique.

Keywords

• chromatically
• WHEELS