Application of polynomial method to on-line list colouring of graphs


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) =  u<v,uv∈E(xu−xv)has onemonomial  v∈V x φ(v) v with φ(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 G, 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: Kl+1,1∗(l−1),2∗(k−l), Ks,t,1∗(k−2) (where (s − 1)(t − 1) ≤ 2k − 3), K3∗2,1∗2,2∗(k−4) and K4,3,1∗3,2∗(k−5). These results provide support for the on-line version of Ohba’s conjecture: graphs G with |V (G)| ≤ 2χ(G) are on-line chromatic-choosable. © 2011 Elsevier Ltd. All rights reserved.


0 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)