On Group Choosability of Graphs,II |
| |
Authors: | H Chuang H-J Lai G R Omidi K Wang N Zakeri |
| |
Institution: | 1. Department of Mathematical Sciences, Isfahan University of Technology, 84156-83111, Isfahan, Iran 2. College of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, Xinjiang, Peoples Republic of China 3. Department of Mathematics, West Virginia University, Morgantown, WV, 26505, USA 4. School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O.Box 19395-5746, Tehran, Iran
|
| |
Abstract: | Given a group A and a directed graph G, let F(G, A) denote the set of all maps ${f : E(G) \rightarrow A}$ . Fix an orientation of G and a list assignment ${L : V(G) \mapsto 2^A}$ . For an ${f \in F(G, A)}$ , G is (A, L, f)-colorable if there exists a map ${c:V(G) \mapsto \cup_{v \in V(G)}L(v)}$ such that ${c(v) \in L(v)}$ , ${\forall v \in V(G)}$ and ${c(x)-c(y)\neq f(xy)}$ for every edge e = xy directed from x to y. If for any ${f\in F(G,A)}$ , G has an (A, L, f)-coloring, then G is (A, L)-colorable. If G is (A, L)-colorable for any group A of order at least k and for any k-list assignment ${L:V(G) \rightarrow 2^A}$ , then G is k-group choosable. The group choice number, denoted by ${\chi_{gl}(G)}$ , is the minimum k such that G is k-group choosable. In this paper, we prove that every planar graph is 5-group choosable, and every planar graph with girth at least 5 is 3-group choosable. We also consider extensions of these results to graphs that do not have a K 5 or a K 3,3 as a minor, and discuss group choosability versions of Hadwiger’s and Woodall’s conjectures. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|