On-line choice number of complete multipartite graphs: An algorithmic approach

Fei Huang Chang, Jun-Yi Guo, Hong Bin Chen, Yu Pei Huang

Research output: Contribution to journalArticle

Abstract

This paper studies the on-line choice number of complete multipartite graphs with independence number m. We give a unified strategy for every prescribed m.Our main result leads to several interesting consequences comparable to known results. (1) If (Formula Presented)where kp denotes the number of parts of cardinality p, then G is on-line chromatic-choosable. (2) If (Formula Presented)then G is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs Km*k is at most k for (Formula Presented).

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume22
Issue number1
Publication statusPublished - 2015 Jan 2

    Fingerprint

Keywords

  • Ohba’s conjecture
  • On-line list coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this