Flexibility of planar graphs of girth at least six |
| |
| Authors: | Zdeněk Dvořák Tomáš Masařík Jan Musílek Ondřej Pangrác |
| |
| Affiliation: | 1. Computer Science Institute (CSI), Charles University in Prague, Prague, Czech Republic;2. Department of Applied Mathematics, Charles University in Prague, Prague, Czech Republic |
| |
| Abstract: | Let be a planar graph with a list assignment . Suppose a preferred color is given for some of the vertices. We prove that if has girth at least six and all lists have size at least three, then there exists an -coloring respecting at least a constant fraction of the preferences. |
| |
| Keywords: | coloring flexibility girth six planar graph |
|
|
