List-Coloring Claw-Free Graphs with Small Clique Number |
| |
| Authors: | Louis Esperet András Gyárfás Frédéric Maffray |
| |
| Institution: | 1. CNRS/Grenoble-INP/UJF-Grenoble 1, G-SCOP (UMR5272), Grenoble, France
2. Rényi Institute, Budapest, Hungary
|
| |
| Abstract: | Chudnovsky and Seymour proved that every connected claw-free graph that contains a stable set of size 3 has chromatic number at most twice its clique number. We improve this for small clique size, showing that every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable. These bounds are tight. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
