Flows, view obstructions, and the lonely runner. (English) Zbl 0910.05064

Bienia, Wojciech; Goddyn, Luis; Gvozdjak, Pavol; Sebő, András; Tarsi, Michael

J. Comb. Theory, Ser. B 72, No. 1, 1-9 (1998).

It is shown that every undirected graph \(G\) for which a flow with at most \(k\) different positive values exists has also a flow with all values in the set \(\{1,2,\dots, k\}\). A flow is an orientation of the edges of \(G\) together with a vector of nonnegative values indexed by the edges such that for each node \(v\) the sum of the values of the edges entering \(v\) is the same as the sum of the values of the edges leaving \(v\). For \(k\geq 5\) the result is a trivial consequence of Seymour’s “six flow theorem.” For \(k\leq 4\) the proof is based on a number-theoretic result of T. W. Cusick and C. Pomerance for which a short proof is given in this paper.

Reviewer: Martin Middendorf (Karlsruhe)

MSC:

05C99	Graph theory
90B10	Deterministic network models in operations research

Keywords:

flow

References:

[1]	Betke, U.; Wills, J. M., Untere Schranken für zwei diophantische Approximations-Funktionen, Monatsch. Math., 76, 214-217 (1972) · Zbl 0239.10016
[2]	Chen, Y. G., On a conjecture about diophantine approximations, I, Acta Math. Sinica, 33, 712-717 (1990) · Zbl 0716.11030
[3]	Cusick, T. W., View-obstruction problems, Aequationes Math., 9, 165-170 (1973) · Zbl 0265.52003
[4]	Cusick, T. W., View-obstruction problems in n-dimensional geometry, J. Combin. Theory Ser. A, 16, 1-11 (1974) · Zbl 0273.10025
[5]	Cusick, T. W., View-obstruction problems, II, Proc. Amer. Math. Soc., 84, 25-28 (1982) · Zbl 0474.10023
[6]	Cusick, T. W.; Pomerance, C., View-obstruction problems, III, J. Number Theory, 19, 131-139 (1984) · Zbl 0563.10026
[7]	Ford, L. R.; Fulkerson, D. R., Network flow and systems of representatives, Canad. J. Math., 10, 78-84 (1958) · Zbl 0080.01102
[8]	Hoffman, A. J., Some recent applications of the theory of linear inequalities to external combinatorial analysis, Proc. Sympos. Appl. Math. (1960), Amer. Math. Soc: Amer. Math. Soc Providence, p. 113-127 · Zbl 0096.00606
[9]	Jaeger, F., Nowhere-zero flow problems, (Beineke, L. W.; Wilson, R., Selected Topics in Graph Theory (1988), Academic Press: Academic Press San Diego), 71-95 · Zbl 0658.05034
[10]	Jaeger, F., Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B, 26, 205-216 (1979) · Zbl 0422.05028
[11]	Oxley, J. G., Matroid Theory (1992), Oxford Univ. Press: Oxford Univ. Press Oxford · Zbl 0784.05002
[12]	Seymour, P. D., Decomposition of regular matroids, J. Combin. Theory Ser. B, 28, 305-359 (1980) · Zbl 0443.05027
[13]	Seymour, P. D., Sowhere-zero 6-flows, J. Combin. Theory Ser. B, 30, 130-135 (1981) · Zbl 0474.05028
[14]	Seymour, P. D., Nowhere-zero flows: Appendix: Colouring, stable sets and perfect graphs, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), Elsevier: Elsevier Amsterdam), 289-299 · Zbl 0845.05035
[15]	Tarsi, M., Nowhere-zero flow and circuit covering in regular matroids, J. Combin. Theory Ser. B, 39, 346-352 (1985) · Zbl 0584.05018
[16]	Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
[17]	Wills, J. M., Zwei Sätze über inhomogene diophantische Approximation von Irrationalzahlen, Monatsch. Math., 71, 263-269 (1967) · Zbl 0148.27505
[18]	Wills, J. M., Zur simultanen homogenen diophantischen Approximation, I, Monatsch. Math., 72, 254-263 (1968) · Zbl 0188.10602
[19]	Wills, J. M., Zur simultanen homogenen diophantischen Approximation, II, Monatsch. Math., 72, 268-281 (1968) · Zbl 0188.10602
[20]	Wills, J. M., Zur simultanen homogenen diophantischen Approximation, III, Monatsch. Math., 74, 166-171 (1970)
[21]	Wills, J. M., Zur simultanen homogenen diophantischen Approximation, Zahlentheorie (Tagung, Math. Forschungsinst. Oberwolfach, 1970), 223-227 (1971) · Zbl 0219.10034