Pearls in Graph Theory

Last updated

Pearls in Graph Theory: A Comprehensive Introduction is an undergraduate-level textbook on graph theory by Nora Hartsfield and Gerhard Ringel. It was published in 1990 by Academic Press [1] [2] [3] with a revised edition in 1994 [4] and a paperback reprint of the revised edition by Dover Books in 2003. [5] The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries. [5]

Contents

Topics

The "pearls" of the title include theorems, proofs, problems, and examples in graph theory. The book has ten chapters; after an introductory chapter on basic definitions, the remaining chapters material on graph coloring; Hamiltonian cycles and Euler tours; extremal graph theory; subgraph counting problems including connections to permutations, derangements, and Cayley's formula; graph labelings; planar graphs, the four color theorem, and the circle packing theorem; near-planar graphs; and graph embedding on topological surfaces. [4] [5]

The book also includes several unsolved problems such as the Oberwolfach problem on covering complete graphs by cycles, the characterization of magic graphs, and Ringel's Earth–Moon problem on coloring biplanar graphs. [3]

Despite its subtitle "A comprehensive introduction", the book is short and its selection of topics reflects author Ringel's personal interests. [1] [5] . Important topics in graph theory that are not covered [1] [4] include the symmetries of graphs, cliques, connections between graphs and linear algebra including adjacency matrices, algebraic graph theory and spectral graph theory, connectivity of a graph (or even biconnected components), Hall's marriage theorem, line graphs, interval graphs, and the theory of tournaments. There is also only one chapter of coverage on algorithms and real-world applications of graph theory. [1] [4] [5] Also, the book omits "difficult or long proofs". [2] [5]

Audience and reception

The book is written as a lower-level undergraduate textbook and recommends that students using it have previously taken a course in discrete mathematics. Nevertheless, it can be read and understood by students with only a high school background in mathematics. Reviewer L. W. Beineke writes that the variety of levels of the exercises is one of the strengths of the book, [4] and reviewer John S. Maybee writes that they are "extensive" and provide interesting connections to additional topics; [1] however, reviewer J. Sedláček criticizes them as "routine". [2]

Although several reviewers complained about the book's spotty or missing coverage of important topics, [1] [4] [5] reviewer Joan Hutchinson praised its choice of topics as "refreshingly different" and noted that, among many previous texts on graph theory, none had as much depth of coverage of topological graph theory. [3] Other reviewer complaints include a misattributed example, [2] a bad definition of the components of a graph that failed to apply to graphs with one component, [5] and a proof of the five-color theorem that only applies to special planar maps instead of all planar graphs. [3]

Despite these complaints, Beineke writes that, as an undergraduate text, "this book has much to offer". [4] Maybee writes that the book was "a joy to read", provided better depth of coverage on some topics than previous graph theory texts, and would be helpful reading for "many graph theorists". [1] Hutchinson praises it as providing "a splendid, enticingly elementary yet comprehensive introduction to topological graph theory". [3]

Related Research Articles

<span class="mw-page-title-main">Four color theorem</span> Statement in mathematics

In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. The proof has gained wide acceptance since then, although some doubters remain.

<span class="mw-page-title-main">Three utilities problem</span> Mathematical puzzle of avoiding crossings

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).

<span class="mw-page-title-main">Gerhard Ringel</span> German-American mathematician

Gerhard Ringel was a German mathematician. He was one of the pioneers in graph theory and contributed significantly to the proof of the Heawood conjecture, a mathematical problem closely linked with the four color theorem.

In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the same set of vertices, such that the union of these planar graphs is G, then the thickness of G is at most k. In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph G.

<span class="mw-page-title-main">Penny graph</span> Graph formed by touching unit circles

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators is a book on graph coloring, Ramsey theory, and the history of development of these areas, concentrating in particular on the Hadwiger–Nelson problem and on the biography of Bartel Leendert van der Waerden. It was written by Alexander Soifer and published by Springer-Verlag in 2009 (ISBN 978-0-387-74640-1).

Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry is a graduate-level mathematics textbook in topological combinatorics. It describes the use of results in topology, and in particular the Borsuk–Ulam theorem, to prove theorems in combinatorics and discrete geometry. It was written by Czech mathematician Jiří Matoušek, and published in 2003 by Springer-Verlag in their Universitext series (ISBN 978-3-540-00362-5).

<i>A Guide to the Classification Theorem for Compact Surfaces</i> Textbook in topology

A Guide to the Classification Theorem for Compact Surfaces is a textbook in topology, on the classification of two-dimensional surfaces. It was written by Jean Gallier and Dianna Xu, and published in 2013 by Springer-Verlag as volume 9 of their Geometry and Computing series. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries.

Art Gallery Theorems and Algorithms is a mathematical monograph on topics related to the art gallery problem, on finding positions for guards within a polygonal museum floorplan so that all points of the museum are visible to at least one guard, and on related problems in computational geometry concerning polygons. It was written by Joseph O'Rourke, and published in 1987 in the International Series of Monographs on Computer Science of the Oxford University Press. Only 1000 copies were produced before the book went out of print, so to keep this material accessible O'Rourke has made a pdf version of the book available online.

Polyhedra is a book on polyhedra, by Peter T. Cromwell. It was published by in 1997 by the Cambridge University Press, with an unrevised paperback edition in 1999.

Euler's Gem: The Polyhedron Formula and the Birth of Topology is a book on the formula for the Euler characteristic of convex polyhedra and its connections to the history of topology. It was written by David Richeson and published in 2008 by the Princeton University Press, with a paperback edition in 2012. It won the 2010 Euler Book Prize of the Mathematical Association of America.

Introduction to Circle Packing: The Theory of Discrete Analytic Functions is a mathematical monograph concerning systems of tangent circles and the circle packing theorem. It was written by Kenneth Stephenson and published in 2005 by the Cambridge University Press.

<i>Crossing Numbers of Graphs</i>

Crossing Numbers of Graphs is a book in mathematics, on the minimum number of edge crossings needed in graph drawings. It was written by Marcus Schaefer, a professor of computer science at DePaul University, and published in 2018 by the CRC Press in their book series Discrete Mathematics and its Applications.

<i>The Petersen Graph</i>

The Petersen Graph is a mathematics book about the Petersen graph and its applications in graph theory. It was written by Derek Holton and John Sheehan, and published in 1993 by the Cambridge University Press as volume 7 in their Australian Mathematical Society Lecture Series.

<i>Graph Theory, 1736–1936</i>

Graph Theory, 1736–1936 is a book in the history of mathematics on graph theory. It focuses on the foundational documents of the field, beginning with the 1736 paper of Leonhard Euler on the Seven Bridges of Königsberg and ending with the first textbook on the subject, published in 1936 by Dénes Kőnig. Graph Theory, 1736–1936 was edited by Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson, and published in 1976 by the Clarendon Press. The Oxford University Press published a paperback second edition in 1986, with a corrected reprint in 1998.

Combinatorics: The Rota Way is a mathematics textbook on algebraic combinatorics, based on the lectures and lecture notes of Gian-Carlo Rota in his courses at the Massachusetts Institute of Technology. It was put into book form by Joseph P. S. Kung and Catherine Yan, two of Rota's students, and published in 2009 by the Cambridge University Press in their Cambridge Mathematical Library book series, listing Kung, Rota, and Yan as its authors. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

<i>Incidence and Symmetry in Design and Architecture</i>

Incidence and Symmetry in Design and Architecture is a book on symmetry, graph theory, and their applications in architecture, aimed at architecture students. It was written by Jenny Baglivo and Jack E. Graver and published in 1983 by Cambridge University Press in their Cambridge Urban and Architectural Studies book series. It won an Alpha Sigma Nu Book Award in 1983, and has been recommended for undergraduate mathematics libraries by the Basic Library List Committee of the Mathematical Association of America.

Introduction to Lattices and Order is a mathematical textbook on order theory by Brian A. Davey and Hilary Priestley. It was published by the Cambridge University Press in their Cambridge Mathematical Textbooks series in 1990, with a second edition in 2002. The second edition is significantly different in its topics and organization, and was revised to incorporate recent developments in the area, especially in its applications to computer science. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

Independence Theory in Combinatorics: An Introductory Account with Applications to Graphs and Transversals is an undergraduate-level mathematics textbook on the theory of matroids. It was written by Victor Bryant and Hazel Perfect, and published in 1980 by Chapman & Hall.

References

  1. 1 2 3 4 5 6 7 "Review of Pearls in Graph Theory (1st ed.)", SIAM Review , 33 (4): 664–665, December 1991, JSTOR   2031030
  2. 1 2 3 4 Sedláček, J., "Review of Pearls in Graph Theory (1st ed.)", zbMATH , Zbl   0703.05001
  3. 1 2 3 4 5 Hutchinson, Joan P. (November 1991), "Review of Pearls in Graph Theory (revised ed.)", American Mathematical Monthly , 98 (9): 873–875, doi:10.2307/2324291, JSTOR   2324291
  4. 1 2 3 4 5 6 7 Beineke, L. W. (March 1996), "Review of Pearls in Graph Theory (revised ed.)", SIAM Review , 38 (1): 159, doi:10.1137/1038017, JSTOR   2132980 ; see also Beineke's shorter review in MR 1282717
  5. 1 2 3 4 5 6 7 8 Hunacek, Mark (September 2015), "Review of Pearls in Graph Theory (Dover ed.)", MAA Reviews, Mathematical Association of America
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.