Skip to content

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

ISBN-10: 111809137X

ISBN-13: 9781118091371

Edition: 2012

Authors: Michael Stiebitz, Lene M. Favrholdt, Bjarne Toft, Diego Scheide

List price: $165.95
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!


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 historial context throughout. Chapter coverage includes an introduction to coloring preliminaries and lower and upper bounds; the Vizing fan; the Kierstead path; simple graphs and line graphs of multigraphs; the Tashkinov tree; Goldberg's conjecture; extreme graphs; generalized edge coloring; and open problems. It serves as a reference for researchers interested in discrete mathematics, graph theory, operations research, theoretical computer science, and combinatorial optimization, as well as a graduate-level course book for students of mathematics, optimization, and computer science.
Customers also bought

Book details

List price: $165.95
Copyright year: 2012
Publisher: John Wiley & Sons, Incorporated
Publication date: 1/30/2012
Binding: Hardcover
Pages: 344
Size: 6.40" wide x 9.30" long x 1.00" tall
Weight: 1.408
Language: English

Coloring Preliminaries
Critical Graphs
Lower Bounds and Elementary Graphs
Upper Bounds and Coloring Algorithms
Vizing Fans
The Fan Equation and the Classical Bounds
Adjacency Lemmas
The Second Fan Equation
The Double Fan
The Fan Number
Kierstead Paths
Kierstead's Method
Short Kierstead's Paths
Simple Graphs and Line Graphs
Class One and Class Two Graphs
Graphs whose Core has Maximum Degree Two
Simple Overfull Graphs
Adjacency Lemmas for Critical Class Two Graphs
Average Degree of Critical Class Two Graphs
Independent Vertices in Critical Class Two Graphs
Constructions of Critical Class Two Graphs
Hadwiger's Conjecture for Line Graphs
Simple Graphs on Surfaces
Tashkinov Trees
Tashkinov's Method
Extended Tashkinov Trees
Asymptotic Bounds
Tashkinov's Coloring Algorithm
Polynomial Time Algorithms
Goldberg's Conjecture
Density and Fractional Chromatic Index
Balanced Tashkinov Trees
Approximation Algorithms
Goldberg's Conjecture for Small Graphs
Another Classification Problem for Graphs
Extreme Graphs
Shannon's Bound and Ring Graphs
Vizing's Bound and Extreme Graphs
Extreme Graphs and Elementary Graphs
Upper Bounds for �' Depending on � and �
Generalized Edge Colorings of Graphs
Equitable and Balanced Edge Colorings
Full Edge Colorings and the Cover Index
Edge Colorings of Weighted Graphs
The Fan Equation for the Chromatic Index �<sup>&#8242;</sup><sub>f</sub>
Decomposing Graphs into Simple Graphs
Twenty Pretty Edge Coloring Conjectures
Vizing's Two Fundamental Papers
On an Estimate of the Chromatic Class of a p-Graph
Critical Graphs with a Given Chromatic Class
Fractional Edge Colorings
The Fractional Chromatic Index
The Matching Polytope
A Formula for �<sup>&#8242;*</sup><sub>f</sub>
Symbol Index
Name Index
Subject Index