Graph Theory in Memory of G.A. Dirac (eBook)

Front Cover 1
Graph Theory in Memory of G.A. Dirac 4
Copyright Page 5
Contents 8
Preface 6
Chapter 1. Gabriel Andrew Dirac 16
Chapter 2. Hamilton Cycles in Metacirculant Graphs with Prime Power Cardinal Blocks 22
Chapter 3. The Edge-Distinguishing Chromatic Number of Paths and Cycles 32
Chapter 4. On the 2-Linkage Problem for Semicomplete Digraphs 38
Chapter 5. The Fascination of Minimal Graphs 54
Chapter 6. Optimal Paths and Cycles in Weighted Graphs 68
Chapter 7. A Note on Hamiltonian Graphs 86
Chapter 8. Uniqueness of the Biggs-Smith Graph 90
Chapter 9. Some Complete Bipartite Graph – Tree Ramsey Numbers 94
Chapter 10. The Edge-Chromatic Class of Graphs with Maximum Degree at Least IVI – 3 106
Chapter 11. On some Aspects of my Work with Gabriel Dirac 126
Chapter 12. Bandwidth versus Bandsize 132
Chapter 13. Circumference and Hamiltonism in K 1,3-Free Graphs 146
Chapter 14. The Prism of a 2-Connected, Planar, Cubic Graph is Hamiltonian 156
Chapter 15. A Note Concerning some Conjectures on Cyclically 4-Edge Connected 3-Regular Graphs 186
Chapter 16. On Connectivity Properties of Eulerian Digraphs 194
Chapter 17. Some Problems and Results on Infinite Graphs 210
Chapter 18. On a Problem Concerning Longest Circuits in Polyhedral Graphs 226
Chapter 19. Interpolation Theorems for the Independence and Domination Numbers of Spanning Trees 236
Chapter 20. Ein zum Vierfarbensatz Äquivalenter Satz der Panisochromie 244
Chapter 21.The Existence Problem for Graph Homomorphisms 270
Chapter 22. On Edge-Colorings of Cubic Graphs and a Formula of Roger Penrose 282
Chapter 23. Longest ab– Paths in Regular Graphs 296
Chapter 24. On Independent Circuits in Finite Graphs and a Conjecture of Erdös and Pósa 314
Chapter 25. Contractions to Complete Graphs 322
Chapter 26. Triangulated Graphs with Marked Vertices 326
Chapter 27. On a Problem upon Configurations Contained in Graphs with Given Chromatic Number 340
Chapter 28. On Disjoint Paths in Graphs 348
Chapter 29. Conjecture de Hadwiger: Un Graphe K-Chromatique Contraction-Critique n’est pas K-Régulier 356
Chapter 30. A Theorem on Matchings in the Plane 362
Chapter 31. Removing Monotone Cycles from Orientations 370
Chapter 32. Disentangling Pairings in Trees 378
Chapter 33. Colour-Critical Graphs with Vertices of Low Valency 386
Chapter 34. About the Chromatic Number of 1-Embeddable Graphs 412
Chapter 35. Problems and Conjectures in the Combinatorial Theory of Ordered Sets 416
Chapter 36. A Proof of Kuratowski’s Theorem 432
Chapter 37. Finite and Infinite Graphs whose Spanning Trees are Pairwise Isomorphic 436
Chapter 38. Bridges of Longest Circuits Applied to the Circumference of Regular Graphs 452
Chapter 39. On a Standard Method Concerning Embeddings of Graphs 468
Chapter 40. Construction of Critical Graphs by Replacing Edges 488
Chapter 41. A Brief History of Hamiltonian Graphs 502
Chapter 42. Erinnerungen an Gabriel Dirac in Hamburg 512
Chapter 43. Hamilton Paths in Multipartite Oriented Graphs 514
Chapter 44. Problems 530