Free Choosability of Outerplanar Graphs |
| |
Authors: | Yves Aubry Jean-Christophe Godin Olivier Togni |
| |
Institution: | 1.Institut de Mathématiques de Toulon,Université de Toulon,La Garde,France;2.Institut de Mathématiques de Marseille,Marseille,France;3.LE2I UMR 6306, CNRS, Arts et Métiers,Université Bourgogne Franche-Comté,DIJON,France |
| |
Abstract: | A graph G is free (a, b)-choosable if for any vertex v with b colors assigned and for any list of colors of size a associated with each vertex \(u\ne v\), the coloring can be completed by choosing for u a subset of b colors such that adjacent vertices are colored with disjoint color sets. In this note, a necessary and sufficient condition for a cycle to be free (a, b)-choosable is given. As a corollary, we obtain almost optimal results about the free (a, b)-choosability of outerplanar graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|