Group Connectivity and Group Colorings of Graphs -- A Survey

作     者：Hong-Jian LAI Xiangwen LI Yehong SHAO Mingquan ZHAN 

作者机构：College of Mathematics and System Sciences Xinjiang University Urumqi 830046 P. R. China Department of Mathematics West Virginia University Morgantown WV26506 USA Department of Mathematics Huazhong Normal University Wuhan 430070 P. R. China Department of Mathematics Ohio University Southern Campus Ironton OH 45638 USA Department of Mathematics Millersville University of Pennsylvania Millersville PA 17551 USA 

出 版 物：《Acta Mathematica Sinica,English Series》 (数学学报（英文版）)

年 卷 期：2011年第27卷第3期

页      面：405-434页

核心收录：

学科分类：07[理学] 08[工学] 070104[理学-应用数学] 081201[工学-计算机系统结构] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Group connectivity group connectivity number group coloring group chromatic number 

摘      要：In 1950s, Tutte introduced the theory of nowhere-zero flows as a tool to investigate the coloring problem of maps, together with his most fascinating conjectures on nowhere-zero flows. These have been extended by Jaeger et al. in 1992 to group connectivity, the nonhomogeneous form of nowhere-zero flows. Let G be a 2-edge-connected undirected graph, A be an （additive） abelian group and A＊ = A - {0}. The graph G is A-connected if G has an orientation D（G） such that for every map b ： V（G） → A satisfying ∑v∈V（G）b（v） ： 0, there is a function f ： E（G） → A＊ such that for each vertex v ∈ V（G）, the total amount of f-values on the edges directed out from v minus the total amount of f-values on the edges directed into v is equal to b（v）. The group coloring of a graph arises from the dual concept of group connectivity. There have been lots of investigations on these subjects. This survey provides a summary of researches on group connectivity and group colorings of graphs. It contains the following sections. 1. Nowhere-zero Flows and Group Connectivity of Graphs 2. Complete Families and A-reductions 3. Reductions with Edge-deletions, Vertex-deletions and Vertex-splitting 4. Group Colorings as a Dual Concept of Group Connectivity 5. Brooks Theorem, Its Variations and Dual Forms 6. Planar Graphs 7. Group Connectivity of Graphs 7.1 Highly Connected Graphs and Collapsible Graphs 7.2 Degrees Conditions 7.3 Complementary Graphs 7.4 Products of Graphs 7.5 Graphs with Diameter at Most 2 7.6 Line Graphs and Claw-Free Graphs 7.7 Triangular Graphs 7.8 Claw-decompositions and All Tutte-orientations