

浏览全部资源
扫码关注微信
新疆大学数学与系统科学学院,新疆大学数学与系统科学学院 新疆乌鲁木齐830046,新疆,乌鲁木齐,830046
Published:2006
移动端阅览
[1]王国平,黄琼湘.复合图点列表着色的可选性(英文)[J].新疆大学学报(自然科学版),2006(02):137-140.
王国平, 黄琼湘. 复合图点列表着色的可选性(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2006, (2).
r部完全图Km*r是完全图Kr与空图Sm的复合图Kr[Sm] . Erdo。s P
Rubin A L和Taylor H在[1]提到了确定Kr[Sm]的点列表着色的可选性的问题并证明了ch(Kr[S2]) = r .Kierstead H A[2]证明了ch(Kr[S3]) =[(4r - 1)/3] .假定Gm是圈Cn与空图Sm的复合图Cn[Sm] .考虑了Gm的列表着色的可选性并证明了ch(G2) =3
ch(G3)≤ 4及在n是奇数时
ch(G3) = 4 .
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.
ERDO。S P, Rubin A L, Taylor H. Choosability in graphs[J].Congr Numer, 1979,26:125-157.
KIERSTEAD H A. Note on the choosability ofcomplete multipartite graphs with part size three[J]. Discrete Math, 2000,211:255-259.
VIZING V G. Coloring the vertices of a graph in prescribed colors[J]. Disc Anal, 1976, 29:3-10.
TUZA Z. Graph colorings with local constraints-a survey[J]. DiscussionesMathematicae Graph Theorey, 1997,17 (2):161-228.
GRAVIER S, Maffray F. Graphs whose choice numberis equal to their chromatic number[J]. J Graph Theory, 1998, 27:87-97.
0
Views
31
下载量
0
CSCD
Publicity Resources
Related Articles
Related Author
Related Institution
京公网安备11010802024621