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 P. J. Heawood, On the four-colour map theorem, Quart. J. Math. 19(1898), 270-285.
- 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
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 55 (1976), 237-242
- MSC: Primary 05C99
- DOI: https://doi.org/10.1090/S0002-9939-1976-0427156-5
- MathSciNet review: 0427156