Balanced valuations and flows in multigraphs

Jaeger, F.

doi:10.1090/S0002-9939-1976-0427156-5

Balanced valuations and flows in multigraphs
HTML articles powered by AMS MathViewer

by F. Jaeger PDF

Proc. Amer. Math. Soc. 55 (1976), 237-242 Request permission

Abstract:

A balanced valuation of a multigraph $H$ is a mapping $w$ of its vertex-set $V(H)$ into $R$ such that $\forall S \subseteq V(H)$ the number of edges of $H$ with exactly one vertex in $S$ is greater than or equal to $|{\sum _{v \in S}}w(v)|$; we apply the theory of flows in networks to obtain known and new results on balanced valuations such as: A cubic multigraph has chromatic index $3$ if and only if it has a balanced valuation with values in $\{ - 2, + 2\}$ (Bondy [5]). Every planar cubic $2$-edge connected multigraph has a balanced valuation with values in $\{ - 5/3, + 5/3\}$. Every planar $5$-regular $4$-edge connected multigraph has a balanced valuation with values in $\{ - 3, + 3\}$.

References

Claude Berge, Graphes et hypergraphes, Collection Dunod Université, Série Violette, No. 604, Dunod, Paris-Brussels-Montreal, Que., 1973 (French). Deuxième édition. MR 0357171
Oystein Ore, The four-color problem, Pure and Applied Mathematics, Vol. 27, Academic Press, New York-London, 1967. MR 0216979
George J. Minty, A Theorem on $n$-Coloring the Points of a Linear Graph, Amer. Math. Monthly 69 (1962), no. 7, 623–624. MR 1531770, DOI 10.2307/2310826

On the four-colour map theorem

19

J. A. Bondy, Balanced colourings and the four colour conjecture, Proc. Amer. Math. Soc. 33 (1972), 241–244. MR 294173, DOI 10.1090/S0002-9939-1972-0294173-4
S. L. Hakimi, On the degrees of the vertices of a directed graph, J. Franklin Inst. 279 (1965), 290–308. MR 180501, DOI 10.1016/0016-0032(65)90340-6
Herbert Grötzsch, Zur Theorie der diskreten Gebilde. V. Beziehungen zwischen Vierkant- und Dreikantnetzen auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 7 (1958), 353–358 (German). MR 116318
W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1–47. MR 179781
W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80–91. MR 61366, DOI 10.4153/cjm-1954-010-9
F. Jaeger, On nowhere-zero flows in multigraphs, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976, pp. 373–378. MR 0395778
George J. Minty, A theorem on three-coloring the edges of a trivalent graph, J. Combinatorial Theory 2 (1967), 164–167. MR 205877