×

Equivalent versions of group-connectivity theorems and conjectures. (English) Zbl 1406.05055

Summary: We present equivalent versions of a conjecture of F. Jaeger et al. [J. Comb. Theory, Ser. B 56, No. 2, 165–182 (1992; Zbl 0824.05043)] that every 5-edge-connected graph is \(\mathbb{Z}_3\)-connected and theorem of L. M. Lovász et al. [ibid. 103, No. 5, 587–598 (2013; Zbl 1301.05154)] that every 6-edge-connected graph is \(\mathbb{Z}_3\)-connected. In particular, we prove that every \((6, 4, 3, 3)\)-edge-connected graph is \(\mathbb{Z}_3\)-connected (a graph \(G\) is \((k, k_1, \ldots, k_n)\)-edge-connected, \(k > k_1 \geq \cdots \geq k_n\), if \(G\) has an ordered set of vertices \(U = (u_1, \ldots, u_n)\) such that each edge-cut that separates \(u_i\) from \(U \setminus \{u_i \}\) has cardinality at least \(k_i\), \(i = 1, \ldots, n\), and all other edge-cuts of \(G\) have cardinality at least \(k\)).

MSC:

05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen, F.; Ning, B., A note on nowhere-zero \(3\)-flow and \(Z_3\)-connectivity, Ars Math. Contemp., 10, 91-98 (2016) · Zbl 1337.05050
[2] da Silva, C. N.; Lucchesi, C. L., \(3\)-flows and combs, J. Graph Theory, 77, 260-277 (2014) · Zbl 1303.05077
[3] de Almeida e. Silva, L. M., Fluxos inteiros em grafos (1991), Dept. of Computer Science, University of Campinas, (in Portuguese)
[4] Fan, G.; Lai, H.-J.; Xu, R.; Zhang, C.-Q.; Zhou, C., Nowhere-zero \(3\)-flows in triangularly connected graphs, J. Combin. Theory Ser. B, 98, 1325-1336 (2008) · Zbl 1171.05026
[5] Han, M.; Lai, H.-J.; Li, J., Nowhere-zero \(3\)-flow and \(Z_3\)-connectedness in graphs with four edge-disjoint spanning trees, J. Graph Theory, 88, 577-591 (2018) · Zbl 1393.05138
[6] Jaeger, F., On circular flows in graphs, (Hajnal, A.; Lovász, L.; Sós, V. T., Finite and Infinite Sets (1984), North-Holland: North-Holland Amsterdam), 391-402 · Zbl 0567.05049
[7] Jaeger, F., Nowhere-zero flow problems, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory 3 (1988), Academic Press: Academic Press New York), 71-95
[8] Jaeger, F.; Linial, N.; Payan, C.; Tarsi, M., Group connectivity of graphs - a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B, 56, 165-182 (1992) · Zbl 0824.05043
[9] Jensen, T.; Toft, B., Unsolved graph colouring problems, (Beineke, L. W.; Wilson, R. J., Topics in Chromatic Graph Theory (2015), Cambridge University Press: Cambridge University Press Cambridge), 327-357 · Zbl 1377.05064
[10] Kochol, M., An equivalent version of the \(3\)-flow conjecture, J. Combin. Theory Ser. B, 83, 258-261 (2001) · Zbl 1029.05088
[11] Kochol, M., Superposition and constructions of graphs without nowhere-zero \(k\)-flows, European J. Combin., 23, 281-306 (2002) · Zbl 1010.05062
[12] Lai, H.-J., Group connectivity of \(3\)-edge-connected chordal graphs, Graphs Combin., 16, 165-176 (2000) · Zbl 0966.05041
[13] Lai, H.-J.; Luo, R.; Zhang, C.-Q., Integer flows and orientations, (Beineke, L. W.; Wilson, R. J., Topics in Chromatic Graph Theory (2015), Cambridge University Press: Cambridge University Press Cambridge), 181-198 · Zbl 1359.05053
[14] Li, J., Group Connectivity and Modulo Orientations of Graphs (2018), West Virginia University: West Virginia University Morgantown, WV, (Ph.D. thesis)
[15] Lovász, L. M.; Thomassen, C.; Wu, Y.; Zhang, C.-Q., Nowhere-zero \(3\)-flows and modulo \(k\)-orientations, J. Combin. Theory Ser. B, 103, 587-598 (2013) · Zbl 1301.05154
[16] Thomassen, C., The weak \(3\)-flow conjecture and the weak circular flow conjecture, J. Combin. Theory Ser. B, 102, 521-529 (2012) · Zbl 1239.05083
[17] Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.