## Graph theory.(English)Zbl 0182.57702

1. Discovery (“short stories” on various ways graphs were discovered by various people). 2. Graphs (contains most of the fundamental terms in graph theory; also includes Ramsey’s problem, extremal graphs, and operations on graphs). 3. Blocks (the structure of graphs, including cut-points and bridges). 4. Trees (presents numerous characterizations of trees; also contains a discussion of matroids). 5. Connectivity (contains many variations of Menger’s Theorem). 6. Partitions (in the sense of degree sequences). 7. Traversability (Eulerian graphs and Hamiltonian graphs). 8. Line-Graphs (including proofs of characterizations of graphs which are line-graphs). 9. Factorization (regular factorization and acyclic factorization). 10. Coverings (discussion of covering numbers and independence numbers). 11. Planarity (includes a proof of Kuratowski’s theorem; also contains discussion of genus, thickness, coarseness, and crossing number). 12. Colorability (includes a discussion of the Four Color Conjecture and a proof of the Five Color Theorem; also considers the Heawood Map, Coloring Theorem, chromatic-critical graphs, homomorphisms, and chromatic polynomials). 13. Matrices (the Matrix-Tree Theorem is proved here). 14. Groups (presents several operations on permutation groups; also discusses Cayley’s color-graph of a group and the $$n$$-cages). 15. Enumeration (Pólya’s Enumeration Theorem is proved; also a detailed discussion is given of solved and unsolved graphical enumeration problems). 16. Digraphs (digraph connectedness and tournaments).
The text is followed by appendices which give: (1) the number of graphs with $$p$$ points and $$q$$ lines, for $$p\leq 9$$, (2) diagrams of all graphs with $$p\leq 6$$ points, (3) the number of digraphs with $$p$$ points and $$q$$ arcs, for $$p\leq 8$$, (4) diagrams of all digraphs with $$p\leq 4$$ points, (5) the number of identity trees and homeomorphically irreducible trees with $$p$$ points, for $$p\leq 12$$, (6) the number of trees and rooted trees with $$p$$ points, for $$p\leq 26$$, (7) diagrams of all trees with $$p\leq 10$$ points. The book concludes with an extensive bibliography; moreover, the text is well-referenced throughout.