×

zbMATH — the first resource for mathematics

Short proofs of classical theorems. (English) Zbl 1031.05046
Summary: We give proofs of Ore’s theorem on Hamilton circuits, Brooks’ theorem on vertex coloring, and Vizing’s theorem on edge coloring, as well as the Chvátal-Lovász theorem on semi-kernels [see V. Chvátal and V. Lovász, Lect. Notes Math. 411, 175 (1974; Zbl 0297.05116)], a theorem of Lu on spanning arborescences of tournaments [see X. Lu, J. Graph. Theory 22, 335-346 (1996; Zbl 0858.05034)], and a theorem of Gutin on diameters of orientations of graphs [cf. G. Gutin, Graphs Comb. 10, 225-230 (1994; Zbl 0814.05044)]. These proofs, while not radically different from existing ones, are perhaps simpler and more natural.

MSC:
05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] and Digraphs. Theory, algorithms, and applications, Springer Monographs in Mathematics, Springer-Verlag London, London, 2001, p. 62. · Zbl 0958.05002
[2] Brooks, Proc Cambridge Philos Soc 37 pp 194– (1941)
[3] Chartrand, SIAM J Appl Math 16 pp 696– (1968)
[4] and Every directed graph has a semi-kernel, in Hypergraph Seminar, and editors, Springer-Verlag, New York, 1974, p. 175. · Zbl 0297.05116
[5] Dirac, Proc London Math Soc 2 pp 69– (1952)
[6] Ehrenfeucht, Discrete Math 52 pp 159– (1984)
[7] Flood, Operations Res 4 pp 61– (1956)
[8] Fournier, Cahiers Centre Études Recherche Opér 15 pp 311– (1973)
[9] Gupta, Notices Amer Math Soc 13 pp 66t– (1966)
[10] Gutin, Graphs Combin 10 pp 225– (1994)
[11] Lovász, J Combin Theory Ser B 19 pp 111– (1975)
[12] Lu, J Graph Theory 22 pp 335– (1996)
[13] Lu, Discrete Math 184 pp 259– (1998)
[14] Newman, Amer Math Monthly 65 pp 611– (1958)
[15] Ore, Amer Math Monthly 67 pp 55– (1960)
[16] Vizing, Diskret Analiz 3 pp 25– (1964)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.