As a natural generalization of graph coloring, Vince
introduced the star chromatic number of a graph
G and denoted it by
$
\chi {\left( G \right)} \geqslant \frac{{n + 3}}
{2}
$
\chi {\left( G \right)} \geqslant \frac{{n + 3}}
{2}
, then
c(M(G))=(M(G)). Let S be the set of vertices of degree
n–1 in
G. It is proved that if
|S|
3, then
c(M(G))=(M(G)), and if |S| 5, then c(M2(G))=(M2(G)), which implies the known results of
Chang, Huang, and Zhu that if n3, c(M(Kn))=(M(Kn)), and if
n5, then
c(M2(Kn))=(M2(Kn)).Mathematics Subject
Classification (2000): 05C15
* Research supported by Grants from National Science
Foundation of China and Chinese Academy of
Sciences.