Adaptable choosability of planar graphs with sparse short cycles |
| |
Authors: | Albert Guan |
| |
Affiliation: | Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan National Center for Theoretical Sciences, Taiwan |
| |
Abstract: | Given a (possibly improper) edge colouring F of a graph G, a vertex colouring of G is adapted toF if no colour appears at the same time on an edge and on its two endpoints. A graph G is called (for some positive integer k) if for any list assignment L to the vertices of G, with |L(v)|≥k for all v, and any edge colouring F of G, G admits a colouring c adapted to F where c(v)∈L(v) for all v. This paper proves that a planar graph G is adaptably 3-choosable if any two triangles in G have distance at least 2 and no triangle is adjacent to a 4-cycle. |
| |
Keywords: | Adapted colouring List colouring Planar graphs |
本文献已被 ScienceDirect 等数据库收录! |
|