Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Abstract view

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

 Printed: Jun 2016
  • Haihui Zhang,
    School of Mathematical Science, Huaiyin Normal University, , $111$ Changjiang West Road, Huaian, Jiangsu, $223300$, P. R. China
Format:   LaTeX   MathJax   PDF  


A graph $G=(V,E)$ is $L$-colorable if for a given list assignment $L=\{L(v):v\in V(G)\}$, there exists a proper coloring $c$ of $G$ such that $c(v)\in L(v)$ for all $v\in V$. If $G$ is $L$-colorable for every list assignment $L$ with $|L(v)|\geq k$ for all $v\in V$, then $G$ is said to be $k$-choosable. Montassier (Inform. Process. Lett. 99 (2006) 68-71) conjectured that every planar graph without cycles of length 4, 5, 6, is 3-choosable. In this paper, we prove that every planar graph without 5-, 6- and 10-cycles, and without two triangles at distance less than 3 is 3-choosable.
Keywords: choosability, planar graph, cycle choosability, planar graph, cycle
MSC Classifications: 05C15 show english descriptions Coloring of graphs and hypergraphs 05C15 - Coloring of graphs and hypergraphs

© Canadian Mathematical Society, 2018 :