A Note on 3-choosability of Planar Graphs Related to Montanssier's Conjecture

Canadian mathematical bulletin

Haihui Zhang¹ 

[1] School of Mathematical Science, Huaiyin Normal University, , $111$ Changjiang West Road, Huaian, Jiangsu, $223300$, P. R. China

关键词: choosability;    planar graph;    cycle;   

DOI  :  10.4153/CMB-2015-040-0

学科分类：数学（综合）

来源: University of Toronto Press * Journals Division

【 摘 要 】

A graph $G=(V,E)$ is $L$-colorable if for a given listassignment $L={L(v):vin V(G)}$, there exists a proper coloring$c$ of $G$ such that $c(v)in L(v)$ for all $vin V$. If $G$ is$L$-colorable for every list assignment $L$ with $|L(v)|geqk$ forall $vin V$, then $G$ is said to be $k$-choosable. Montassier (Inform. Process. Lett. 99 (2006) 68-71) conjectured that everyplanargraph without cycles of length 4, 5, 6, is 3-choosable. In thispaper,we prove that every planar graph without 5-, 6- and 10-cycles,andwithout two triangles at distance less than 3 is 3-choosable.

【 授权许可】

Unknown