Premium
Coupled choosability of plane graphs
Author(s) -
Wang Weifan,
Lih KoWei
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20292
Subject(s) - combinatorics , mathematics , vertex (graph theory) , planar graph , list coloring , plane (geometry) , graph , 1 planar graph , discrete mathematics , graph power , chordal graph , line graph , geometry
A plane graph G is coupled k ‐choosable if, for any list assignment L satisfying $|{{L}}({{x}})|= {{k}}$ for every ${{x}}\in {{V}}({{G}})\cup {{F}}({{G}})$ , there is a coloring that assigns to each vertex and each face a color from its list such that any two adjacent or incident elements receive distinct colors. We prove that every plane graph is coupled 7‐choosable. We further show that maximal plane graphs, ${{K}}_{{4}}$ ‐minor free graphs, and plane graphs with maximum degree at most three are coupled 6‐choosable. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 27–44, 2008