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 languageEnglish
Pages (from-to)872-883
Number of pages12
JournalEuropean Journal of Combinatorics
Volume33
Issue number5
DOIs
Publication statusPublished - 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.

Cite this