\(Z_3\)-connectivity of claw-free graphs. (English) Zbl 1365.05158
Summary: F. Jaeger et al. [J. Comb. Theory, Ser. B 56, No. 2, 165–182 (1992; Zbl 0824.05043)] conjectured that every 5-edge-connected graph is \(Z_3\)-connected, which is equivalent to that every 5-edge-connected claw-free graph is \(Z_3\)-connected by H.-J. Lai et al. [Inf. Process. Lett. 111, No. 23–24, 1085–1088 (2011; Zbl 1260.05121)], and J. Ma and X. Li [Discrete Math. 336, 57–68 (2014; Zbl 1300.05117)]. Let \(G\) be a claw-free graph on at least 3 vertices such that there are at least two common neighbors of every pair of 2-distant vertices. In this paper, we prove that \(G\) is not \(Z_3\)-connected if and only if \(G\) is one of seven specified graphs, or three families of well characterized graphs. As a corollary, \(G\) does not admit a nowhere-zero 3-flow if and only if \(G\) is one of three specified graphs or a family of well characterized graphs.
MSC:
| 05C40 | Connectivity |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, Berlin (2008) · Zbl 1134.05001 · doi:10.1007/978-1-84628-970-5 |
| [2] | Chen, J., Eschen, E., Lai, H.-J.: Group connectivity of certain graphs. Ars Comb. 89, 141-158 (2008) · Zbl 1224.05267 |
| [3] | Devos, M., Xu, R., Yu, G.: Nowhere-zero \[Z_3\] Z3-flows through \[Z_3\] Z3-connectivity. Discret. Math. 306, 26-30 (2006) · Zbl 1086.05043 · doi:10.1016/j.disc.2005.10.019 |
| [4] | Fan, G., Zhou, C.: Ore condition and nowhere-zero 3-flows. SIAM J. Discret. Math. 22, 288-294 (2008) · Zbl 1170.05025 · doi:10.1137/060677744 |
| [5] | 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 · doi:10.1016/j.jctb.2008.02.008 |
| [6] | Jaeger, F., Linial, N., Payan, C., Tarsi, N.: 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 |
| [7] | 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 |
| [8] | Lai, H.-J.: Group connectivity of 3-edge-connected chordal graphs. Graphs Combin. 16, 165-176 (2000) · Zbl 0966.05041 · doi:10.1007/s003730050014 |
| [9] | Lai, H.-J.: Nowhere-zero 3-flows in locally connected graphs. J. Graph Theory 42, 211-219 (2003) · Zbl 1015.05037 · doi:10.1002/jgt.10085 |
| [10] | Lai, H.-J., Li, H., Li, P., Liang, Y., Yao, S.: Mod (2p+1)-orientations in line graphs. Inf. Process. Lett. 111, 1085-1088 (2011) · Zbl 1260.05121 · doi:10.1016/j.ipl.2011.09.005 |
| [11] | Lai, H.-J., Li, X., Shao, Y., Zhan, M.: Group connectivity and group colorings of graphs—a survey. Acta Math. Sin. (Engl. Ser.) 27, 405-434 (2011) · Zbl 1233.05127 |
| [12] | Li, X., Shao, Y., Lai, H.-J.: Degree condition and \[Z_3\] Z3-connectivity. Discret. Math. 312, 1658-1669 (2012) · Zbl 1242.05146 · doi:10.1016/j.disc.2012.01.013 |
| [13] | Lovász, L.M., Thomassen, C., Wu, Y., Zhang, C.-Q.: Nowhere-zero 3-flows and modulo \[k\] k-orientations. J. Combin. Theory Ser. B 103, 587-598 (2013) · Zbl 1301.05154 · doi:10.1016/j.jctb.2013.06.003 |
| [14] | Luo, R., Xu, R., Yin, J., Yu, G.: Ore-condition and \[Z_3\] Z3-connectivity. Eur. J. Combin. 29, 1587-1595 (2008) · Zbl 1171.05029 · doi:10.1016/j.ejc.2007.11.014 |
| [15] | Ma, J., Li, X.: Nowhere-zero \[33\]-flows of claw-free graphs. Discret. Math. 336, 57-68 (2014) · Zbl 1300.05117 · doi:10.1016/j.disc.2014.08.001 |
| [16] | Shi, R.: 2-neighborhoods and Hamiltonian conditions. J. Graph Theory 16, 267-271 (1992) · Zbl 0761.05066 · doi:10.1002/jgt.3190160310 |
| [17] | 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 · doi:10.1016/j.jctb.2011.09.003 |
| [18] | Tutte, W.T.: On the imbedding of linear graphs in surfaces. Proc. Lond. Math. Soc. Ser. 2(51), 474-483 (1949) · Zbl 0033.30803 |
| [19] | Tutte, W.T.: A contribution to the theory of chromatic polynomials. Can. J. Math. 6, 80-91 (1954) · Zbl 0055.17101 · doi:10.4153/CJM-1954-010-9 |
| [20] | Yang, F., Li, X.: Degree sum condition for 3-independent set and \[Z_3\] Z3-connectivity. Discret. Math. 313, 2493-2505 (2013) · Zbl 1279.05015 · doi:10.1016/j.disc.2013.07.009 |
| [21] | Zhang, X., Zhan, M., Xu, R., Shao, Y., Li, X., Lai, H.-J.: Degree Sum condition for \[Z_3\] Z3-connectivity in graphs. Discret. Math. 310, 3390-3397 (2010) · Zbl 1210.05028 · doi:10.1016/j.disc.2010.08.004 |
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.
