Minimum choosability of planar graphs |
| |
Authors: | Huijuan Wang Bin Liu Ling Gai Hongwei Du Jianliang Wu |
| |
Affiliation: | 1.School of Mathematics and Statistics,Qingdao University,Qingdao,China;2.Department of Mathematics,Ocean University of China,Qingdao,China;3.School of Management,Shanghai University,Shanghai,China;4.Department of Computer Science and Technology,Harbin Institute of Technology Shenzhen Graduate School,Shenzhen,China;5.School of Mathematics,Shandong University,Jinan,China |
| |
Abstract: | The problem of list coloring of graphs appears in practical problems concerning channel or frequency assignment. In this paper, we study the minimum number of choosability of planar graphs. A graph G is edge-k-choosable if whenever every edge x is assigned with a list of at least k colors, L(x)), there exists an edge coloring (phi ) such that (phi (x) in L(x)). Similarly, A graph G is toal-k-choosable if when every element (edge or vertex) x is assigned with a list of at least k colors, L(x), there exists an total coloring (phi ) such that (phi (x) in L(x)). We proved (chi '_{l}(G)=Delta ) and (chi ''_{l}(G)=Delta +1) for a planar graph G with maximum degree (Delta ge 8) and without chordal 6-cycles, where the list edge chromatic number (chi '_{l}(G)) of G is the smallest integer k such that G is edge-k-choosable and the list total chromatic number (chi ''_{l}(G)) of G is the smallest integer k such that G is total-k-choosable. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|