Pearls in Graph Theory: A Comprehensive Introduction es un libro de texto de nivel de licenciatura sobre teoría de grafos escrito por Nora Hartsfield y Gerhard Ringel . Fue publicado en 1990 por Academic Press [1] [2] [3] con una edición revisada en 1994 [4] y una reimpresión en rústica de la edición revisada por Dover Books en 2003. [5] El Comité de la Lista Básica de Bibliotecas de la Asociación Matemática de Estados Unidos ha sugerido su inclusión en las bibliotecas de matemáticas de pregrado. [5]
Las "perlas" del título incluyen teoremas, demostraciones, problemas y ejemplos de teoría de grafos . El libro tiene diez capítulos; después de un capítulo introductorio sobre definiciones básicas, los capítulos restantes contienen material sobre coloración de grafos ; ciclos hamiltonianos y giros de Euler ; teoría de grafos extremos ; problemas de conteo de subgrafos que incluyen conexiones con permutaciones , desarreglos y la fórmula de Cayley ; etiquetado de grafos ; grafos planares , el teorema de los cuatro colores y el teorema de empaquetamiento circular ; grafos casi planares; e incrustación de grafos en superficies topológicas. [4] [5]
El libro también incluye varios problemas sin resolver, como el problema de Oberwolfach sobre cómo cubrir gráficos completos mediante ciclos, la caracterización de gráficos mágicos y el problema Tierra-Luna de Ringel sobre cómo colorear gráficos biplanares . [3]
A pesar de su subtítulo "Una introducción completa", el libro es breve y su selección de temas refleja los intereses personales del autor Ringel. [1] [5] . Los temas importantes en la teoría de grafos que no se cubren [1] [4] incluyen las simetrías de grafos , las camarillas , las conexiones entre grafos y el álgebra lineal incluyendo matrices de adyacencia , la teoría de grafos algebraicos y la teoría de grafos espectrales , la conectividad de un grafo (o incluso componentes biconectados ), el teorema del matrimonio de Hall , los grafos de línea , los grafos de intervalo y la teoría de torneos . También hay solo un capítulo de cobertura sobre algoritmos y aplicaciones del mundo real de la teoría de grafos. [1] [4] [5] Además, el libro omite "pruebas difíciles o largas". [2] [5]
El libro está escrito como un libro de texto de nivel inferior para estudiantes de grado y se recomienda que los estudiantes que lo utilicen hayan tomado previamente un curso de matemáticas discretas . Sin embargo, puede ser leído y comprendido por estudiantes con solo una formación en matemáticas de secundaria. El revisor LW Beineke escribe que la variedad de niveles de los ejercicios es uno de los puntos fuertes del libro, [4] y el revisor John S. Maybee escribe que son "extensos" y proporcionan conexiones interesantes con temas adicionales; [1] sin embargo, el revisor J. Sedláček los critica como "rutinarios". [2]
Aunque varios críticos se quejaron de la cobertura irregular o faltante del libro de temas importantes, [1] [4] [5] la crítica Joan Hutchinson elogió su elección de temas como "refrescantemente diferente" y señaló que, entre muchos textos anteriores sobre teoría de grafos, ninguno tenía tanta profundidad de cobertura de la teoría de grafos topológicos . [3] Otras quejas de los críticos incluyen un ejemplo mal atribuido, [2] una mala definición de los componentes de un grafo que no se aplica a grafos con un componente, [5] y una prueba del teorema de los cinco colores que solo se aplica a mapas planares especiales en lugar de a todos los grafos planares. [3]
A pesar de estas quejas, Beineke escribe que, como texto de grado, "este libro tiene mucho que ofrecer". [4] Maybee escribe que el libro fue "un placer de leer", proporcionó una mayor profundidad en la cobertura de algunos temas que los textos anteriores de teoría de grafos y sería una lectura útil para "muchos teóricos de grafos". [1] Hutchinson lo elogia por proporcionar "una introducción espléndida, atractivamente elemental pero completa a la teoría de grafos topológicos". [3]