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

by Stiebitz, Michael; Scheide, Diego; Toft, Bjarne; Favrholdt, Lene M.

• ISBN13: 9781118091371
• ISBN10: 111809137X
• Edition: 1st
• Format: Hardcover
• Copyright: 2012-02-14
• Publisher: Wiley

Summary

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.

Author Biography

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.

Table of Contents

Preface	p. xi
Introduction	p. 1
Graphs	p. 1
Coloring Preliminaries	p. 2
Critical Graphs	p. 5
Lower Bounds and Elementary Graphs	p. 6
Upper Bounds and Coloring Algorithms	p. 11
Notes	p. 15
Vizing Fans	p. 19
The Fan Equation and the Classical Bounds	p. 19
Adjacency Lemmas	p. 24
The Second Fan Equation	p. 26
The Double Fan	p. 31
The Fan Number	p. 32
Notes	p. 39
Kierstead Paths	p. 43
Kierstead's Method	p. 43
Short Kierstead's Paths	p. 46
Notes	p. 49
Simple Graphs and Line Graphs	p. 51
Class One and Class Two Graphs	p. 51
Graphs whose Core has Maximum Degree Two	p. 54
Simple Overfull Graphs	p. 63
Adjacency Lemmas for Critical Class Two Graphs	p. 73
Average Degree of Critical Class Two Graphs	p. 84
Independent Vertices in Critical Class Two Graphs	p. 89
Constructions of Critical Class Two Graphs	p. 93
Hadwiger's Conjecture for Line Graphs	p. 101
Simple Graphs on Surfaces	p. 105
Notes	p. 110
Tashkinov Trees	p. 115
Tashkinov's Method	p. 115
Extended Tashkinov Trees	p. 127
Asymptotic Bounds	p. 139
Tashkinov's Coloring Algorithm	p. 144
Polynomial Time Algorithms	p. 148
Notes	p. 152
Goldberg's Conjecture	p. 155
Density and Fractional Chromatic Index	p. 155
Balanced Tashkinov Trees	p. 160
Obstructions	p. 162
Approximation Algorithms	p. 183
Goldberg's Conjecture for Small Graphs	p. 185
Another Classification Problem for Graphs	p. 186
Notes	p. 193
Extreme Graphs	p. 197
Shannon's Bound and Ring Graphs	p. 197
Vizing's Bound and Extreme Graphs	p. 201
Extreme Graphs and Elementary Graphs	p. 203
Upper Bounds for ¿' Depending on ¿ and ¿	p. 205
Notes	p. 209
Generalized Edge Colorings of Graphs	p. 213
Equitable and Balanced Edge Colorings	p. 213
Full Edge Colorings and the Cover Index	p. 222
Edge Colorings of Weighted Graphs	p. 224
The Fan Equation for the Chromatic Index ¿′f	p. 228
Decomposing Graphs into Simple Graphs	p. 239
Notes	p. 243
Twenty Pretty Edge Coloring Conjectures	p. 245
Vizing's Two Fundamental Papers	p. 269
On an Estimate of the Chromatic Class of a p-Graph	p. 269
References	p. 272
Critical Graphs with a Given Chromatic Class	p. 273
References	p. 278
Fractional Edge Colorings	p. 281
The Fractional Chromatic Index	p. 281
The Matching Polytope	p. 284
A Formula for ¿′*f	p. 290
References	p. 295
Symbol Index	p. 312
Name Index	p. 314
Subject Index	p. 318
Table of Contents provided by Ingram. All Rights Reserved.