×

Nowhere-zero 3-flows in triangularly connected graphs. (English) Zbl 1171.05026

Summary: Let \(H_1\) and \(H_2\) be two subgraphs of a graph \(G\). We say that \(G\) is the 2-sum of \(H_1\) and \(H_2\), denoted by \(H_1\oplus _2 H_2\), if \(E(H_1)\cup E(H_2)=E(G)\), \(|V(H_1)\cap V(H_2)|=2\), and \(|E(H_1)-E(H_2)|=1\). A triangle-path in a graph \(G\) is a sequence of distinct triangles \(T_1T_2\dots T_m\) in \(G\) such that for \(1\leq i\leq m-1\), \(|E(T_i)-E(T_{i+1})|=1\) and \(E(T_i)\cap E(T_j)=\emptyset\) if \(j>i+1\). A connected graph \(G\) is triangularly connected if for any two edges \(e\) and \(e'\), which are not parallel, there is a triangle-path \(T_1T_2\dots T_m\) such that \(e\in E(T_1)\) and \(e'\in E(T_m)\). Let \(G\) be a triangularly connected graph with at least three vertices. We prove that \(G\) has no nowhere-zero 3-flow if and only if there is an odd wheel \(W\) and a subgraph \(G_1\) such that \(G=W\oplus_2G_1\), where \(G_1\) is a triangularly connected graph without nowhere-zero 3-flow. Repeatedly applying the result, we have a complete characterization of triangularly connected graphs which have no nowhere-zero 3-flow. As a consequence, \(G\) has a nowhere-zero 3-flow if it contains at most three 3-cuts. This verifies Tutte’s 3-flow conjecture and an equivalent version by Kochol for triangularly connected graphs. By the characterization, we obtain extensions to earlier results on locally connected graphs, chordal graphs and squares of graphs. As a corollary, we obtain a result of J. Barát and C. Thomassen [J. Graph Theory 52, No. 2, 135–146 (2006; Zbl 1117.05088)] that every triangulation of a surface admits all generalized Tutte-orientations.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity

Citations:

Zbl 1117.05088
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barát, J.; Thomassen, C., Claw-decompositions and Tutte-orientations, J. Graph Theory, 52, 135-146 (2006) · Zbl 1117.05088
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North-Holland: North-Holland New York · Zbl 1134.05001
[3] DeVos, M.; Xu, R.; Yu, G., Nowhere-zero \(Z_3\)-flows through \(Z_3\)-connectivity, Discrete Math., 306, 26-30 (2006) · Zbl 1086.05043
[4] 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
[5] Jensen, T. R.; Toft, B., Graph Coloring Problems (1995), John Wiley & Sons: John Wiley & Sons New York · Zbl 0971.05046
[6] Kochol, M., An equivalent version of the 3-flow conjecture, J. Combin. Theory Ser. B, 83, 258-261 (2001) · Zbl 1029.05088
[7] Kochol, M., Superposition and constructions of graphs without nowhere-zero \(k\)-flows, European J. Combin., 23, 281-306 (2002) · Zbl 1010.05062
[8] Lai, H. J., Group connectivity of 3-edge-connected chordal graphs, Graphs Combin., 16, 165-176 (2000) · Zbl 0966.05041
[9] Lai, H. J., Nowhere-zero 3-flows in locally connected graphs, J. Graph Theory, 42, 211-219 (2003) · Zbl 1015.05037
[10] 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
[11] Xu, R.; Zhang, C.-Q., Nowhere-zero 3-flows in squares of graphs, Electron. J. Combin., 10, R5 (2003) · Zbl 1018.05031
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.