Geodesic
On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 2, pp. 237-244

Voir la notice de l'article provenant de la source Library of Science

A graph G is said to be chromatic-choosable if ch(G) = χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. In this paper we show that Ohba's conjecture is true for complete multipartite graphs K_4,3*t,2*(k-2t-2),1*(t+1) for all integers t ≥ 1 and k ≥ 2t+2, that is, ch(K_4,3*t,2*(k-2t-2),1*(t+1)) = k, which extends the results ch(K_4,3,2*(k-4),1*2) = k given by Shen et al. (Discrete Math. 308 (2008) 136-143), and ch(K_4,3*2,2*(k-6),1*3) = k given by He et al. (Discrete Math. 308 (2008) 5871-5877).
Keywords: list coloring, complete multipartite graphs, chromatic-choosable graphs, Ohba's conjecture 
@article{DMGT_2010_30_2_a3,
     author = {Zheng, Guo-Ping and Shen, Yu-Fa and Chen, Zuo-Li and Lv, Jin-Feng},
     title = {On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {237--244},
     publisher = {mathdoc},
     volume = {30},
     number = {2},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a3/}
}
TY  - JOUR
AU  - Zheng, Guo-Ping
AU  - Shen, Yu-Fa
AU  - Chen, Zuo-Li
AU  - Lv, Jin-Feng
TI  - On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 237
EP  - 244
VL  - 30
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a3/
LA  - en
ID  - DMGT_2010_30_2_a3
ER  - 
%0 Journal Article
%A Zheng, Guo-Ping
%A Shen, Yu-Fa
%A Chen, Zuo-Li
%A Lv, Jin-Feng
%T On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 237-244
%V 30
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a3/
%G en
%F DMGT_2010_30_2_a3
Zheng, Guo-Ping; Shen, Yu-Fa; Chen, Zuo-Li; Lv, Jin-Feng. On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 2, pp. 237-244. http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a3/