Graph Edge Coloring (PDF)

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.