Bordeaux 3-color conjecture and 3-choosability |
| |
Authors: | Mickaël Montassier Weifan Wang |
| |
Institution: | LaBRI UMR CNRS 5800, Université Bordeaux I, 33405 Talence Cedex, France |
| |
Abstract: | A graph G=(V,E) is list L-colorable if for a given list assignment L={L(v):v∈V}, there exists a proper coloring c of G such that c(v)∈L(v) for all v∈V. If G is list L-colorable for every list assignment with |L(v)|?k for all v∈V, then G is said to be k-choosable.In this paper, we prove that (1) every planar graph either without 4- and 5-cycles, and without triangles at distance less than 4, or without 4-, 5- and 6-cycles, and without triangles at distance less than 3 is 3-choosable; (2) there exists a non-3-choosable planar graph without 4-cycles, 5-cycles, and intersecting triangles. These results have some consequences on the Bordeaux 3-color conjecture by Borodin and Raspaud A sufficient condition for planar graphs to be 3-colorable. J. Combin. Theory Ser. B 88 (2003) 17-27]. |
| |
Keywords: | Bordeaux 3-color conjecture Choosability |
本文献已被 ScienceDirect 等数据库收录! |
|