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

Abstract: 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

k_{1} - s u m_{p = 2}^{m} (f r a c p^{2} 2 - f r a c 3 p 2 + 1) k_{p} g e q 0

, where

k_{p}

denotes the number of parts of cardinality

p

, then

G

is on-line chromatic-choosable. (2) If

| V (G) | l e q f r a c m^{2} - m + 2 m^{2} - 3 m + 4 c h i (G)

, then

G

is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs

K_{m s t a r k}

is at most

(m + f r a c 12 - s q r t 2 m - 2) k

for

m g e q 3

.

Full work available at URL: https://arxiv.org/abs/1305.2700

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (2)

This page was built for publication: On-line choice number of complete multipartite graphs: an algorithmic approach