科研之友
微信
新浪微博
Facebook
分享链接
摘要
A graph is on-line chromatic choosable if its on-line choice number equals its chromatic number. In this paper, we consider on-line chromatic-choosable complete multi-partite graphs. Assume G is a complete k-partite graph. It is known that if the polynomial P(G) defined as P(G) = Pi(u<v,uv is an element of E)(x(u) - X-v) has one monomial Pi(v is an element of V) x(v)(phi(v)) with phi(v) < k whose coefficient is nonzero, then G is on-line k-choosable. It is usually difficult to calculate the coefficient of a monomial in P(G). For several classes of complete multi-partite graphs C. we introduce different polynomials Q(G) associated to G, such that Q(G) and P(G) have the same coefficient for those monomials of highest degree. However, the calculation of the coefficient of some monomials based on Q(G) is easier. Using this method, we prove the following graphs are on-line k-choosable: K-l 1.1*(l-1),K-2*(k-l), K-s,K-t,K-1*(k-2) (where (s - 1)(t - 1) <= 2k - 3), K3*2.1*2.2*(k-4) and K-4,K-3,K-1*3,K-2*(k-5). These results provide support for the on-line version of Ohba's conjecture: graphs G with vertical bar V(G)vertical bar <= 2 chi(G) are on-line chromatic-choosable.
