Application of polynomial method to on-line list colouring of graphs
- Huang, Po-Yi
- Wong, Tsai-Lien
- Zhu, Xuding
DOIAbstract
AbstractA 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...
Add to ORKG