scientific article; zbMATH DE number 3241107
Die Graphentheorie hat in den letzten Jahren an Bedeutung und allgemeinem Interesse zugenommen. Das vermeintlich tiefstliegende und zugleich aber auch verfänglichste Problem der Graphentheorie ist das berühmte (bis heute noch ungelöste) Vierfarbenproblem. Es besagt, in jedem ebenen Graphen \(G\) kann jede Ecke von \(G\) mit je einer Farbe immer so gefärbt werden, daß\ erstens je zwei benachbarte (d.\,h. durch eine Kante von \(G\) verbundene) Ecken von \(G\) stets mit zwei verschiedenen Farben gefärbt sind und man zweitens bei der Färbung aller Ecken von \(G\) mit 4 oder weniger Farben auskommt. Nach einem historischen Rückblick über das Vierfarbenproblem behandelt Verf. in den beiden ersten Kapiteln zunächst die ebenen Graphen, insbesondere ebene Dreiecksgraphen. Kapitel 3--5 machen den Leser mit einigen besonders interessanten Typen von Graphen bekannt: duale, paare (bipartite), reguläre Graphen, sowie Graphen, die eine Hamiltonsche Linie besitzen. In den Kapiteln 6--9 sind Färbungen von Graphen (Ecken-, Kanten- und Länder-Färbungen) behandelt. Sie vermitteln einen interessanten Einblick in die eigenartige Problematik der Färbungstheorie von Graphen. Im Kap.\,10 erlebt der aufmerksame Leser eine große Überraschung. Das Vierfarbenproblem erscheint hier, losgelöst von der Ebene, als Teil eines allgemeinen Problems der Hadwiger-Vermutung. Die überaus reizvollen Begriffe der Graphentheorie: Homomorphis (subcontraction), simpliziale Zerfällungen von Graphen und Homomorphie-Basis, werden sehr ausführlich besprochen. Dem Studium eines weiteren sehr reizvollen Begriffs der Graphentheorie: kritische Graphen (critical graphs), ist Kap.\,11 gewidmet. Schließlich befassen sich die letzten drei Kapitel 12--14 vorwiegend wieder mit ebenen Graphen. Zum Beispiel wird bewiesen, daß\ der Vierfarbensatz für alle ebenen Graphen mit höchstens 35 Ecken richtig ist. Zusammenfassend möchte Ref. über das neue Buch des bekannten Verfassers sagen, daß\ hier ein ganz hervorragendes Werk über das Viefarbenproblem vorliegt. Es ist von Anfang bis Ende spannend und überaus klar geschrieben. Der Kenner des Vierfarbenproblems wird viele neue Anregungen finden. Aber auch der junge Studierende der Mathematik wird das Buch mit Erfolg lesen können und sehr bald seine Freude an den sinnreichen Methoden und Schlüssen der Graphentheorie haben. Ein reichhaltiges Schriftenverzeichnis, ein Namen- und Sachverzeichnis bilden den Abschluß\ des Buches.
- Intersection properties of boxes in \(R^ n\).
- On 1-factorizability of Cayley graphs
- Simplicial schemes
- Independent sets in k-chromatic graphs
- On Tutte polynomials and cycles of plane graphs
- An algorithm for the characterization of the nonplanarity of a maximal graphical partition
- Matching extension and the genus of a graph
- A graph-theoretical characterization of the order complexes on the 2- sphere
- On the Penrose number of cubic diagrams
- Flows and generalized coloring theorems in graphs
- Interval matroids and graphs
- On a covering problem of Mullin and Stanton for binary matroids
- Some counterexamples associated with the three-color problem
- On the geometry of semigroup presentations
- The enumeration problem for color critical linear hypergraphs
- Critical hypergraphs for the weak chromatic number
- Kempe classes and the Hadwiger conjecture
- Graphs having circuits with at least two chords
- On the enumeration of chains in regular chain-groups
- Shortness parameters of families of regular planar graphs in two or three types of faces
- On the existence and connectivity of a class of maximal planar graphs
- On the thickness of graphs of given degree
- Note on inscribability of quadrangular polyhedra with restricted number of edge-types
- A linear-time algorithm for finding an ambitus
- On Hadwiger's number---A problem of the Nordhaus-Gaddum type
- 6-valent analogues of Eberhard's theorem
- Über minimale, nichtprojektive Graphen mit einer Kreuzhaube
- The importance of being Euler
- A practical approach to the chromatic partition problem
- On parity patterns of even q-angulations
- Properties of a planar cubic graph
- Excess in critical graphs
- Zum Basisproblem der nicht in die projektive Ebene einbettbaren Graphen. II
- Change graphs of edge-colourings of planar cubic graphs
- Separation of vertices by a circuit
- Über die Querstücke minimaler, nicht-projektiver Graphen. II
- Pairs of Hamiltonian circuits in 5-connected planar graphs
- Transformations of edge-colourings of cubic graphs
- Inégalités nouvelles dans le problème des quatre couleurs
- The four-color theorem for small maps
- Orienting planar graphs
- Über n-fach zusammenhängende Eckenmengen in Graphen
- Cycles Hamiltoniens dans les graphes 4-réguliers 4-connexes
- Développements recents de la théorie des graphes
- Pairs of edge-disjoint Hamiltonian circuits
- On the depth of a planar graph
- Un metodo canonico di riduzione e costruzione relativo a grafi planari massimali
- Bridges and Hamiltonian circuits in planar graphs
- Some 4-valent, 3-connected, planar, almost pancyclic graphs
- Geometric coloring theory
- Dichte Klassen konvexer Polytope
- Hamiltonian circuits in prisms over certain simple 3-polytopes
- Contractions of graphs: A theorem of Ore and an extremal problem
- Su di un problema di A. M. Hobbs
- Hajos' graph-coloring conjecture: Variations and counterexamples
- A remark on noncolorable cubic graphs
- On an extension of the Grinberg theorem
- Colouring problems
- Lower bounds on the cover-index of a graph
- Sulla cardinabilita delle classi di 6-5-grafi
- An unavoidable set of configurations in planar trigangulations
- The reconstruction of maximal planar graphs. II: Reconstruction
- Triangles with restricted degrees of their boundary vertices in plane triangulations
- A note on partial 3-trees and homomorphism bases of graphs
- Edge-reconstruction of minimally 3-connected planar graphs
- Minors of quasi 4-connected graphs
- Extending matchings in graphs: A survey
- Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces
- At most single-bend embeddings of cubic graphs
- On the colorability of \(m\)-composed graphs
- Diagonal flips in triangulations of surfaces
- On the edge-reconstruction of 3-connected planar graphs with minimum valency 4
- Connectivity and \(\beta\)-invariants of isotropic systems and 4-regular graphs
- A new proof of Grünbaum's 3 color theorem
- On Vizing's theorem, adjacency lemma and fan argument generalized to multigraphs
- A note on graph colorings and graph polynomials
- A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
- On weakly starlike multivalent functions
- A new lower bound on the number of edges in colour-critical graphs and hypergraphs
- Generating \(r\)-regular graphs
- A theorem on graphs
- A planarity criterion for cubic bipartite graphs
- Penrose's ideas on the 4-color-problem
- Density of 5/2-critical graphs
- Complete colorings of planar graphs
- Critical \((P_6, \mathrm{banner})\)-free graphs
- Hadwiger's conjecture and inflations of the Petersen graph
- On spin models, triply regular association schemes, and duality
- Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
- Generating rooted triangulations without repetitions
- Signed diagonal flips and the four color theorem
- The class reconstruction number of maximal planar graphs
- Even subgraph expansions for the flow polynomial of cubic plane maps
- Graphes cubiques d'indice trois, graphes cubiques isochromatiques, graphes cubiques d'indice quatre
- The number of edge 3-colorings of a planar cubic graph as a permanent
- A lower bound for the independence number of a planar graph
- Minimal vertex Ramsey graphs and minimal forbidden subgraphs
- Planar triangulations which quadrangulate other surfaces
- Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
- Transformations of cubic graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5528475)