Perlas en teoría de grafos

Pearls in Graph Theory: A Comprehensive Introduction es un libro de texto de nivel universitario 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 América 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 en 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 tratan sobre coloración de grafos ; ciclos hamiltonianos y recorridos eulerianos ; teoría extremal de grafos ; problemas de conteo de subgrafos, incluyendo conexiones con permutaciones , desordenamientos y la fórmula de Cayley ; etiquetado de grafos ; grafos planares , el teorema de los cuatro colores y el teorema del empaquetamiento de círculos ; 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 el recubrimiento de grafos completos mediante ciclos , la caracterización de grafos mágicos y el problema Tierra-Luna de Ringel sobre la coloración de grafos biplanares . ^{[ 3 ]}

A pesar de su subtítulo "Una introducción completa", el libro es corto y su selección de temas refleja los intereses personales del autor Ringel. ^{[ 1 ] [ 5 ]} Temas importantes en teoría de grafos que no se cubren ^{[ 1 ] [ 4 ]} incluyen simetrías de grafos , cliques , conexiones entre grafos y álgebra lineal, incluyendo matrices de adyacencia , teoría algebraica de grafos y teoría espectral de grafos , conectividad de un grafo (o incluso componentes biconexas ), el teorema del matrimonio de Hall , grafos de línea , grafos de intervalo y la teoría de torneos . También hay solo un capítulo sobre algoritmos y aplicaciones del mundo real de la teoría de grafos. ^{[ 1 ] [ 4 ] [ 5 ]} Además, el libro omite "demostraciones difíciles o largas". ^{[ 2 ] [ 5 ]}

El libro está escrito como un libro de texto de nivel básico para estudiantes de pregrado y recomienda que los estudiantes que lo utilicen hayan cursado previamente matemáticas discretas . Sin embargo, puede ser leído y comprendido por estudiantes con solo conocimientos de matemáticas de nivel de bachillerato. El crítico LW Beineke escribe que la variedad de niveles de los ejercicios es uno de los puntos fuertes del libro, ^{[ 4 ]} y el crítico John S. Maybee escribe que son "extensos" y proporcionan conexiones interesantes con otros temas; ^{[ 1 ]} sin embargo, el crítico J. Sedláček los critica por ser "rutinarios". ^{[ 2 ]}

Aunque varios revisores se quejaron de la cobertura irregular o incompleta del libro sobre temas importantes, ^{[ 1 ] [ 4 ] [ 5 ]} la revisora ​​Joan Hutchinson elogió su selección de temas como "refrescantemente diferente" y señaló que, entre muchos textos anteriores sobre teoría de grafos, ninguno tenía tanta profundidad en la cobertura de la teoría topológica de grafos . ^{[ 3 ]} Otras quejas de los revisores incluyen un ejemplo mal atribuido, ^{[ 2 ]} una mala definición de los componentes de un grafo que no se aplicaba a grafos con un componente, ^{[ 5 ]} y una demostración 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 pregrado, "este libro tiene mucho que ofrecer". ^{[ 4 ]} Maybee escribe que el libro fue "un placer de leer", proporcionó una cobertura más profunda en 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 topológica de grafos". ^{[ 3 ]}

• Perlas en teoría de grafos (1.ª ed.) en el Archivo de Internet