2013/05/13 by Fei-Huang Chang, Chang, Fei-Huang, Hong-Bin Chen +6
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C10 #msc:05C15
paper · pdf · doi:10.48550/arxiv.1305.2700
arxiv created 2014/12/17 · arxiv updated 2014/12/18
This paper studies the on-line choice number on 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 k1-∑p=2m((p2)/(2)-(3p)/(2)+1)kp≥ 0, where kp denotes the number of parts of cardinality p, then G is on-line chromatic-choosable. (2) If |V(G)|≤(m2-m+2)/(m2-3m+4)χ(G), then G is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs Km⋆ k is at most (m+(1)/(2)-√(2m-2))k for m≥ 3.