Read more
Informationen zum Autor Michael Stiebitz, PhD , is Professor of Mathematics at the Technical University of Ilmenau, Germany. He is the author of numerous journal articles in his areas of research interest, which include graph theory, combinatorics, cryptology, and linear algebra. Diego Scheide, PhD , is a Postdoctoral Researcher in the Department of Mathematics at Simon Fraser University, Canada. Bjarne Toft, PhD , is Associate Professor in the Department of Mathematics and Computer Science at the University of Southern Denmark. Lene M. Favrholdt, PhD , is Associate Professor in the Department of Mathematics and Computer Science at the University of Southern Denmark. Klappentext Features recent advances and new applications in graph edge coloringReviewing recent advances in the Edge Coloring Problem, Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture provides an overview of the current state of the science, explaining the interconnections among the results obtained from important graph theory studies. The authors introduce many new improved proofs of known results to identify and point to possible solutions for open problems in edge coloring.The book begins with an introduction to graph theory and the concept of edge coloring. Subsequent chapters explore important topics such as:* Use of Tashkinov trees to obtain an asymptotic positive solution to Goldberg's conjecture* Application of Vizing fans to obtain both known and new results* Kierstead paths as an alternative to Vizing fans* Classification problem of simple graphs* Generalized edge coloring in which a color may appear more than once at a vertexThis book also features first-time English translations of two groundbreaking papers written by Vadim Vizing on an estimate of the chromatic class of a p-graph and the critical graphs within a given chromatic class.Written by leading experts who have reinvigorated research in the field, Graph Edge Coloring is an excellent book for mathematics, optimization, and computer science courses at the graduate level. The book also serves as a valuable reference for researchers interested in discrete mathematics, graph theory, operations research, theoretical computer science, and combinatorial optimization. Zusammenfassung Written by world authorities on graph theory, this book features many new advances and applications in graph edge coloring, describes how the results are interconnected, and provides historical context throughout. Inhaltsverzeichnis Preface xi 1 Introduction 1 1.1 Graphs 1 1.2 Coloring Preliminaries 2 1.3 Critical Graphs 5 1.4 Lower Bounds and Elementary Graphs 6 1.5 Upper Bounds and Coloring Algorithms 11 1.6 Notes 15 2 Vizing Fans 19 2.1 The Fan Equation and the Classical Bounds 19 2.2 Adjacency Lemmas 24 2.3 The Second Fan Equation 26 2.4 The Double Fan 31 2.5 The Fan Number 32 2.6 Notes 39 3 Kierstead Paths 43 3.1 Kierstead's Method 43 3.2 Short Kierstead's Paths 46 3.3 Notes 49 4 Simple Graphs and Line Graphs 51 4.1 Class One and Class Two Graphs 51 4.2 Graphs whose Core has Maximum Degree Two 54 4.3 Simple Overfull Graphs 63 4.4 Adjacency Lemmas for Critical Class Two Graphs 73 4.5 Average Degree of Critical Class Two Graphs 84 4.6 Independent Vertices in Critical Class Two Graphs 89 4.7 Constructions of Critical Class Two Graphs 93 4.8 Hadwiger's Conjecture for Line Graphs 101 4.9 Simple Graphs on Surfaces 105 4.10 Notes 110 5 Tashkinov Trees 115 5.1 Tashkinov's Method 115 5.2 Extended Tashkinov Trees 127 5.3 Asymptotic Bounds 139 5.4 Tashkinov's Coloring Algorithm 144 5.5 Polynomial Time Algorithms 148 5.6 Notes 152
