Geodesic
On-line choice number of complete multipartite graphs: an algorithmic approach
Fei-Huang Chang1 ; Hong-Bin Chen2 ; Jun-Yi Guo3 ; Yu-Pei Huang4
1Department of Mathematics and Science, National Taiwan Normal University, Taiwan
2Institute of Mathematics, Academia Sinica, Taiwan
3Department of Mathematics, National Taiwan Normal University, Taiwan
4Department of Applied Mathematics, National Chiao Tung University, Taiwan
The electronic journal of combinatorics, Tome 22 (2015) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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-\sum_{p=2}^m\left(\frac{p^2}{2}-\frac{3p}{2}+1\right)k_p\geq 0$, where $k_p$ denotes the number of parts of cardinality $p$, then $G$ is on-line chromatic-choosable. (2) If $|V(G)|\leq\frac{m^2-m+2}{m^2-3m+4}\chi(G)$, then $G$ is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs $K_{m\star k}$ is at most$\left(m+\frac{1}{2}-\sqrt{2m-2}\right)k$ for $m\geq 3$.
DOI : 10.37236/3378
Classification : 05C15, 05C57, 05C85, 05C69
Mots-clés : online list coloring, Ohba's conjecture, paintability

Fei-Huang Chang  1   ; Hong-Bin Chen  2   ; Jun-Yi Guo  3   ; Yu-Pei Huang  4

1 Department of Mathematics and Science, National Taiwan Normal University, Taiwan
2 Institute of Mathematics, Academia Sinica, Taiwan
3 Department of Mathematics, National Taiwan Normal University, Taiwan
4 Department of Applied Mathematics, National Chiao Tung University, Taiwan 
@article{10_37236_3378,
     author = {Fei-Huang Chang and Hong-Bin Chen and Jun-Yi Guo and Yu-Pei Huang},
     title = {On-line choice number of complete multipartite graphs: an algorithmic approach},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {1},
     doi = {10.37236/3378},
     zbl = {1305.05070},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3378/}
}
TY  - JOUR
AU  - Fei-Huang Chang
AU  - Hong-Bin Chen
AU  - Jun-Yi Guo
AU  - Yu-Pei Huang
TI  - On-line choice number of complete multipartite graphs: an algorithmic approach
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3378/
DO  - 10.37236/3378
ID  - 10_37236_3378
ER  - 
%0 Journal Article
%A Fei-Huang Chang
%A Hong-Bin Chen
%A Jun-Yi Guo
%A Yu-Pei Huang
%T On-line choice number of complete multipartite graphs: an algorithmic approach
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3378/
%R 10.37236/3378
%F 10_37236_3378
Fei-Huang Chang; Hong-Bin Chen; Jun-Yi Guo; Yu-Pei Huang. On-line choice number of complete multipartite graphs: an algorithmic approach. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/3378

Cité par Sources :