×

zbMATH — the first resource for mathematics

Group connectivity and group colorings of graphs — a survey. (English) Zbl 1233.05127
Summary: 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) \mapsto A\) satisfying \(\sum_{v\in V(G)} b(v) = 0\), there is a function \(f: E(G) \mapsto A^*\) such that for each vertex \(v \in 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

MSC:
05C40 Connectivity
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, Elsevier, New York, 1976 · Zbl 1226.05083
[2] Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., et al.: Combinatroial Optimization, John Wiley and Sons, New York, 1998
[3] Jaeger, F., Linial, N., Payan, C., et al.: Group connectivity of graphs – a nonhomogeneous analogue of nowhere-zero flow properties. J. Combin. Theory Ser. B, 56, 165–182 (1992) · Zbl 0824.05043 · doi:10.1016/0095-8956(92)90016-Q
[4] Tutte, W. T.: A contribution to the theory of chromatic polynomials. Canad. J. Math., 6, 80–91 (1954) · Zbl 0055.17101 · doi:10.4153/CJM-1954-010-9
[5] Jaeger, F.: Nowhere-zero flow problems. In: Selected Topics in Graph Theory (L. Beineke and R. Wilson, eds.), Vol. 3, Academic Press, London/New York, 1988, 91–95
[6] Tutte, W. T.: On the algebraic theory of graph colourings. J. Combin. Theory, 1, 15–50 (1966) · Zbl 0139.41402 · doi:10.1016/S0021-9800(66)80004-2
[7] Lai, H.-J.: Reduction towards collapsibility. In: Graph Theory, Combinatorics, and Applications (eds. Y. Alavi and A. Schwenk), John Wiley and Sons, Inc., New York, 1995, 661–670 · Zbl 0843.05089
[8] Alon, N., Linial, N., Meshulam, R.: Additive bases of vextor spaces over prime fields. J. Combin. Theory Ser. A, 57, 203–210 (1991) · Zbl 0739.11003 · doi:10.1016/0097-3165(91)90045-I
[9] Kochol, M.: An equivalent version of the 3-flow conjecture. J. Combin. Theory Ser. B, 83, 258–261 (2001) · Zbl 1029.05088 · doi:10.1006/jctb.2001.2054
[10] Lai, H.-J.: Group connectivity of 3-edge-connected chordal graphs. Graphs and Combinatorics, 16, 165–176 (2000) · Zbl 0966.05041 · doi:10.1007/s003730050014
[11] Chen, J., Eschen, E., Lai, H.-J.: Group connectivity of certain graphs. Ars Combin., 89, 141–158 (2008) · Zbl 1224.05267
[12] Devos, M., Xu, R., Yu, G.: Nowhere-zero Z 3-flows through Z 3-connectivity. Discrete Math., 306, 26–30 (2006) · Zbl 1086.05043 · doi:10.1016/j.disc.2005.10.019
[13] Fan, G., Lai, H.-J., Xu, R., et al.: Nowhere-zero 3-flows in triangularly connected graphs. J. Comb. Theory, Ser. B, 98(6), 1325–1336 (2008) · Zbl 1171.05026 · doi:10.1016/j.jctb.2008.02.008
[14] Xu, R.: Ph.D. Dissertation, West Virginia University, 2004
[15] Yao, X., Gong, D.: Group connectivity of Kneser graphs. Intern. J. Algebra, 1, 535–539 (2007) · Zbl 1151.05023
[16] Catlin, P. A.: Double cycle covers and the Petersen graph. J. Graph Theory, 13, 95–116 (1989) · Zbl 0713.05040 · doi:10.1002/jgt.3190130408
[17] Catlin, P. A.: A reduction criterion for supereulerian graphs. J. Graph Theory, 22, 151–153 (1996) · Zbl 0856.05061 · doi:10.1002/(SICI)1097-0118(199606)22:2<151::AID-JGT5>3.0.CO;2-M
[18] Lai, H.-J., Lai, H.: Duality of graph families. Discrete Math., 110, 165–177 (1992) · Zbl 0772.05084 · doi:10.1016/0012-365X(92)90705-K
[19] Catlin, P. A., Hobbs, A. M., Lai, H.-J.: Graph families operations. Discrete Math., 230, 71–97 (2001) · Zbl 0969.05060 · doi:10.1016/S0012-365X(00)00071-6
[20] Lai, H.-J.: Nowhere-zero 3-flows in locally connected graphs. J. Graph Theory, 42(3), 211–219 (2003) · Zbl 1015.05037 · doi:10.1002/jgt.10085
[21] Seymour, P. D.: Nowhere-zero 6-flows. J. Combin. Theory Ser. B., 30, 130–135 (1981) · Zbl 0474.05028 · doi:10.1016/0095-8956(81)90058-7
[22] Lai, H.-J., Miao, L., Shao, Y.: Every line graph of a 4-edge-connected graph is Z 3-connected. European Journal od Combinatorics, 30, 595–601 (2009) · Zbl 1189.05086 · doi:10.1016/j.ejc.2008.02.013
[23] Welsh, D. J. A.: Matroid Theory, Academic Press, London, 1976
[24] Oxley, J.: Matroid Theory, Oxford University Press, New York, 1992 · Zbl 0784.05002
[25] Steinberg, R.: The state of the three color problem. In: Uuo Vadis, Graphs Theory? (eds. J. Gimbel, J. W. Kennedy and L. V. Quintas). Annals of Discrete Mathematics, 55, 211–248 (1993) · Zbl 0791.05044
[26] Aksionov, V. A.: Concerning the extension of the 3-coloring of planar graphs (in Russian). Diskret. Analz., 26, 3–19 (1974)
[27] Grötzsch, H.: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wissenschaftliche Zeitschrisch-Naturwissenschaftiche Reihe, 8, 1958/1959, 109–120
[28] Grübaum, B.: Grötzsch’s theorem on 3-colorings. Michigan Mathematical Journal, 10, 303–310 (1963) · Zbl 0115.40903 · doi:10.1307/mmj/1028998916
[29] Steinberg, R., Younger, D.: Grötzsch’s theorem for the projective plane. Ars Combinatoria, 28, 15–31 (1989) · Zbl 0721.05025
[30] Thomassen, C.: Grötzsch’s 3-color theorem and its counterparts for the torus and the projective plane. J. Combin. Theory Ser. B, 62, 268–297 (1994) · Zbl 0817.05024 · doi:10.1006/jctb.1994.1069
[31] Chen, Z.-H., Lai, H.-J., Lei, X., et al.: Group coloring and group connectivity of graphs. Congressus Numerantium, 134, 123–130 (1998) · Zbl 0952.05031
[32] Lai, H.-J., Zhang, X.: Group colorability of graphs. Ars Combinatoria, 62, 299–317 (2002) · Zbl 1071.05532
[33] Lai, H.-J., Zhang, X.: Group chromatic number of graphs without K 5-minors. Graphs and Combinatorics, 18, 147–154 (2002) · Zbl 0993.05073 · doi:10.1007/s003730200009
[34] Liu, B., Lai, H.-J.: Matrices in Combinatorics and Graph Theory, Kluwer Academic Publishers, Dordrecht, 2000 · Zbl 0958.05003
[35] Li, H.: Ph.D. Dissertation, West Virginia University, to be completed in 2010
[36] Szekeres, G., Wilf, H.: An inequality for the chromatic number of a graph. J. Combin. Theory, 4, 1–3 (1968) · Zbl 0171.44901 · doi:10.1016/S0021-9800(68)80081-X
[37] Lai, H.-J., Li, X., Yu, G.: An inequality for the group chromatic number of a graph. Discrete Math., 307, 3076–3080 (2007) · Zbl 1127.05041 · doi:10.1016/j.disc.2007.03.014
[38] Yao, S.: Ph. D. Dissertation, West Virginia University, to be completed in 2011
[39] Lai, H.-J., Li, X.: Group Chromatic number of graph. Graphs and Combinatorics, 21, 469–474 (2005) · Zbl 1092.05024 · doi:10.1007/s00373-005-0625-0
[40] Li, X., Lai, H.-J., Shao, Y.: Degree condition and Z 3-connectivity. Submitted
[41] Král, D., Pangrác, O., Voss, H.-J.: A note on group colorings. J. Graph Theory, 50, 123–129 (2005) · Zbl 1077.05044 · doi:10.1002/jgt.20098
[42] Wagner, K.: Über eine eigneschaft der ebenen komplexe. Math. Ann., 144, 570–590 (1937) · JFM 63.0550.01 · doi:10.1007/BF01594196
[43] Lai, H.-J., Li, X.: Group Chromatic number of planar graphs with girth at east 4. J. Graph Theory, 52, 51–72 (2006) · Zbl 1088.05032 · doi:10.1002/jgt.20147
[44] Lai, H.-J., Zhang, C.-Q.: Nowhere-zero 3-flows of highly connected graphs. Discrete Math., 110, 179–183 (1992) · Zbl 0809.05063 · doi:10.1016/0012-365X(92)90706-L
[45] Lai, H.-J., Shao, Y., Wu, H., et al.: On mod (2p + 1)-orientations of graphs, J. Combin. Theory, Ser B., 99, 399–406 (2009) · Zbl 1184.05061 · doi:10.1016/j.jctb.2008.08.001
[46] Lai, H.-J.: Extending a partial nowhere-zero 4-flow. J. Graph Theory, 30, 277–288 (1999) · Zbl 0920.05023 · doi:10.1002/(SICI)1097-0118(199904)30:4<277::AID-JGT3>3.0.CO;2-D
[47] Barat, J., Thomassen, C.: Claw-decompositions and Tutte-orientations. J. Graph Theory, 135–146 (2006) · Zbl 1117.05088
[48] Lai, H.-J., Xu, R.: Counterexamples to a Z 3-connected theorem. Submitted
[49] Fan, G., Zhou, C.: Ore-condition and nowhere-zero 3-flows. SIAM J. Discrete Math., 22, 288–294 (2008) · Zbl 1170.05025 · doi:10.1137/060677744
[50] Fan, G., Zhou, C.: Degree sum and nowhere-zero 3-flows. Discrete Math., 308(24), 6233–6240 (2008) · Zbl 1167.05309 · doi:10.1016/j.disc.2007.11.045
[51] Luo, R., Xu, R., Yin, J., Yin, G.: Ore-condition and Z 3-connectivity. European J. Combin., 29, 1587–1595 (2008) · Zbl 1171.05029 · doi:10.1016/j.ejc.2007.11.014
[52] Sun, J., Xu, R., Yin, J.: Group connectivity of graphs satisfying Ore-condition, 2008 International Conference on Foundations of Computer Science, 2008, 21–24
[53] Yao, X., Li, X., Lai, H.-J.: Degree conditions for group connectivity. Discrete Math., 310, 1050–1058 (2010) · Zbl 1231.05160 · doi:10.1016/j.disc.2009.10.023
[54] Zhang, X., Zhan, M., Xu, R., et al.: Z 3-connectivity in graphs satisfying degree sum condition. Discrete Math., accepted
[55] Li, X.: Group chromatic number of planar graphs without intersecting triangles. Submitted
[56] Luo, R., Xu, R., Zang, W., et al.: Realizing degree sequences with graphs having nowhere-zero 3-flows. SIAM J. Discrete Mathematics, 22, 500–519 (2008) · Zbl 1168.05017 · doi:10.1137/070687372
[57] Graham, R., Rothschild, B., Spencer, J.: Ramsey Theory, John Wiley and Sons, New York, 1990
[58] Nebeský, L.: A theorem on hamiltonian line graphs. Comment. Math. Univ. Caroliae, 14, 107–112 (1973) · Zbl 0255.05120
[59] Nebeský, L.: On Eulerian subgraphs of complementary graphs. Czech. Math. J., 29, 298–302 (1979) · Zbl 0394.05033
[60] Lai, H.-J.: Supereulerian complementary graphs. J. Graph Theory, 17, 263–273 (1993) · Zbl 0781.05033 · doi:10.1002/jgt.3190170214
[61] Li, P.: Ph. D. Dissertation, West Virginia University, to be completed in 2012
[62] Hou, X., Lai, H.-J., Li, P., et al.: Group connectivity of complementary graphs. Submitted · Zbl 1242.05173
[63] Gould, R.: Advance on the Hamiltonian problem – A survey. Graphs and Combinatorics, 19, 7–52 (2003) · Zbl 1024.05057 · doi:10.1007/s00373-002-0492-x
[64] Lai, H.-J.: Reduced graphs of diameter 2. J. Graph Theory, 14, 77–87 (1990) · Zbl 0699.05037 · doi:10.1002/jgt.3190140109
[65] Lai, H.-J., Yao, X.: Group connectivity of graphs with diameter at most 2. European J. Combin., 27, 436–447 (2006) · Zbl 1094.05029 · doi:10.1016/j.ejc.2004.11.001
[66] Chen, Z.-H., Lai, H.-J., Lai, H.: Nowhere-zero flows in line graphs. Discrete Math., 230, 133–141 (2001) · Zbl 0982.05080 · doi:10.1016/S0012-365X(00)00076-5
[67] Beineke, L.: Derived graphs and digraphs, Beiträge zur Graphentheorie, Teubner, Leipzig, 1968 · Zbl 0179.29204
[68] Robertson, N.: Unpublished notes, see Page 74 of ”Graph Theory” by F. Harary, Addison-Wesley, Reading Massachusetts, 1969
[69] Ryjáček, Z.: On a closure concept in claw-free graphs. J. Combin. Theory Ser. B, 70, 217–224 (1997) · Zbl 0872.05032 · doi:10.1006/jctb.1996.1732
[70] Shao, Y.: Ph.D. Dissertation, West Virginia University, 2005
[71] Broersma, H. J., Veldman, H. J.: 3-Connected linegraphs of triangular graphs are panconnected and 1- hamiltonian. J. Graph Theory, 11, 399–407 (1987) · Zbl 0656.05045 · doi:10.1002/jgt.3190110314
[72] Xu, R., Zhang, C.-Q.: Nowhere-zero 3-flows in squares of graphs. Electronic Journal of Combinatorics, 10, R5 (2003) · Zbl 1018.05031
[73] Lai, H.-J., Xu, R., Zhou, J.: On group connectivity of graphs. Graphs and Combinatorics, 24, 1–9 (2008) · Zbl 1170.05042 · doi:10.1007/s00373-008-0780-1
[74] Hou, X., Lai, H.-J., Zhan, M., et al.: Z 3-connectivity of 4-edge-connected triangular graphs. Submitted
[75] Lai, H.-J.: Mod (2p + 1)-orientations and K 1,2p+1-decompositions. SIAM J. Discrete Math., 21, 844–850 (2007) · Zbl 1151.05040 · doi:10.1137/060676945
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.