复合图点列表着色的可选性(英文)

The Choosability of the Composition Graphs

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 Km·r with m vertices in each part is the composition graph Kr[Sm] of the complete graph K, by an empty graph Sm with m vertices. Erdos P, Rubin A L, and Taylor H mentioned the problem of determining the choosability of Kr[Sm] and obtained ch（Kr[S2]） = r. Kierstead H A proved ch（Kr[S3]） = [（4r - 1）/3]. Let Gm be the composition graph Cn[Sm] of an n -cycle Cn by Sm. In this paper we consider the problem of determining the choosability of Gm and obtain ch （G2） = 3 and ch （G3） ≤ 4 , and ch （G3） = 4 if n is odd.