×

The weak 3-flow conjecture and the weak circular flow conjecture. (English) Zbl 1239.05083

Summary: We show that, for each natural number \(k>1\), every graph (possibly with multiple edges but with no loops) of edge-connectivity at least \(2k^{2}+k\) has an orientation with any prescribed outdegrees modulo \(k\) provided the prescribed outdegrees satisfy the obvious necessary conditions. For \(k=3\) the edge-connectivity 8 suffices. This implies the weak 3-flow conjecture proposed by F. Jaeger [Selected topics in graph theory, Vol. 3, 71- 95 (1988; Zbl 0658.05034)] (a natural weakening of Tutte’s 3-flow conjecture which is still open) and also a weakened version of the more general circular flow conjecture proposed by F. Jaeger [Colloq. Math. Soc. János Bolyai 37, No. 1, 391–402 (1984; Zbl 0567.05049)]. It also implies the tree-decomposition conjecture proposed in 2006 by Bárat and Thomassen when restricted to stars. Finally, it is the currently strongest partial result on the \((2+\epsilon )\)-flow conjecture by Goddyn and Seymour.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bárat, 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), The MacMillan Press Ltd. · Zbl 1134.05001
[3] Diestel, R., Graph Theory (1997), Springer-Verlag, and 2nd edition, 2000 · Zbl 0873.05001
[4] Dor, D.; Tarsi, M., Graph decomposition is NP-complete: a complete proof of Holyerʼs conjecture, SIAM J. Comput., 26, 1166-1187 (1997) · Zbl 0884.05071
[5] Jaeger, F., On circular flows in graphs, Proc. Colloq. Math. János Bolyai, 391-402 (1982) · Zbl 0567.05049
[6] Jaeger, F., Nowhere-zero flow problems, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, vol. 3 (1988), Academic Press), 71-95 · Zbl 0658.05034
[7] Mohar, B.; Thomassen, C., Graphs on Surfaces (2001), Johns Hopkins University Press · Zbl 0979.05002
[8] Thomassen, C., Decompositions of highly connected graphs into paths of length 4, Abh. Math. Semin. Univ. Hambg., 78, 17-26 (2008) · Zbl 1181.05057
[9] Thomassen, C., Decompositions of highly connected graphs into paths of length 3, J. Graph Theory, 58, 286-292 (2008) · Zbl 1214.05134
[10] C. Thomassen, Decomposing graphs into paths of fixed length, in press.; C. Thomassen, Decomposing graphs into paths of fixed length, in press. · Zbl 1299.05270
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.