Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture

Front Cover
John Wiley & Sons, Feb 27, 2012 - Mathematics - 344 pages
Features recent advances and new applications in graph edge coloring

Reviewing 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 vertex

This 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.

 

What people are saying - Write a review

User Review - Flag as inappropriate

nothing

Contents

Vizings Theorem and Goldbergs Conjecture 1 Introduction
1
Vizings Theorem and Goldbergs Conjecture 2 Vizing Fans
19
Vizings Theorem and Goldbergs Conjecture 3 Kierstead Paths
43
Vizings Theorem and Goldbergs Conjecture 4 Simple Graphs and Line Graphs
51
Vizings Theorem and Goldbergs Conjecture 5 Tashkinov Trees
115
Vizings Theorem and Goldbergs Conjecture 6 Goldbergs Conjecture
155
Vizings Theorem and Goldbergs Conjecture 7 Extreme Graphs
197
Vizings Theorem and Goldbergs Conjecture 8 Generalized Edge Colorings of Graphs
213
Vizings Theorem and Goldbergs Conjecture 9 Twenty Pretty Edge Coloring Conjectures
245
Vizings Theorem and Goldbergs Conjecture Appendix A Vizings Two Fundamental Papers
269
Vizings Theorem and Goldbergs Conjecture Appendix B Fractional Edge Colorings
281
Vizings Theorem and Goldbergs Conjecture References
295
Vizings Theorem and Goldbergs Conjecture Symbol Index
312
Vizings Theorem and Goldbergs Conjecture Name Index
314
Vizings Theorem and Goldbergs Conjecture Subject Index
318
Copyright

Other editions - View all

Common terms and phrases

About the author (2012)

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.

Bibliographic information