Planar graphs without 3-, 7-, and 8-cycles are 3-choosable |
| |
| Authors: | Zdeněk Dvo?á k,Riste &Scaron krekovski |
| |
| Affiliation: | a Department of Applied Mathematics and Inst. for Theoretical Computer Science (ITI), 11Supported by the Ministry of Education of the Czech Republic as project 1M0021620808. Charles University, Malostranské nám. 25, 118 00 Prague, Czech Republic
b Department of Mathematics, University of Ljubljana, Jadranska 21, 1000 Ljubljana, Slovenia |
| |
| Abstract: | A graph G is k-choosable if every vertex of G can be properly colored whenever every vertex has a list of at least k available colors. Grötzsch’s theorem [4] states that every planar triangle-free graph is 3-colorable. However, Voigt [M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995) 325-328] gave an example of such a graph that is not 3-choosable, thus Grötzsch’s theorem does not generalize naturally to choosability. We prove that every planar triangle-free graph without 7- and 8-cycles is 3-choosable. |
| |
| Keywords: | Choosability List-coloring Planar graphs Short cycles |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
