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

Po Yi Huang, Tsai Lien Wong, Xuding Zhu

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

## Abstract

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 one monomial ∏v∈Vxvφ(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: K ℓ+1,1*(ℓ-1),2*(k-ℓ), K s,t,1*(k-2) (where (s-1)(t-1)≤2k-3), K 3*2,1*2,2*(k-4) and K 4,3,1*3,2*(k-5). These results provide support for the on-line version of Ohba's conjecture: graphs G with {pipe}V(G){pipe}≤2χ(G) are on-line chromatic-choosable.

Original language English 872-883 12 European Journal of Combinatorics 33 5 https://doi.org/10.1016/j.ejc.2011.09.020 Published - 2012 Jul

## All Science Journal Classification (ASJC) codes

• Discrete Mathematics and Combinatorics

## Fingerprint

Dive into the research topics of 'Application of polynomial method to on-line list colouring of graphs'. Together they form a unique fingerprint.