The Choosability of the Composition Graphs
Huang Qiongxiang · Shinjang dashösi ilmiy jurnili · 2006
The complete $r$-partite graph $K-{m*r}$ with $m$ vertices in each part is the composition graph $K-r[S-m]$ of the complete graph $K-r$ by an empty graph $S-m$ with $m$ vertices. Erd[AKo¨D]s P, Rubin A L, and Taylor H+{[1]} mentioned the problem of determining the choosability of $K-r[S-m]$ and obtained $ch(K-r[S-2])=r$. Kierstead H A+{[2]} proved $ch(K-r[S-3])=[(4r-1)/3]$. Let $G-m$ be the composition graph $C-n[S-m]$ of an $n$-cycle $C-n$ by $S-m$. In this paper we consider the problem of determining the choosability of $G-m$ and obtain $ch(G-2)=3$ and $ch(G-3)≤4$,and $ch(G-3)=4$ if $n$ is odd.