Graph Edge Coloring: Vizings Theorem and Goldbergs Conjecture

Features recent advances and new applications in graph edgecoloring

Reviewing recent advances in the Edge Coloring Problem, GraphEdge Coloring: Vizing′s Theorem and Goldberg′s Conjectureprovides an overview of the current state of the science,explaining the interconnections among the results obtained fromimportant graph theory studies. The authors introduce many newimproved proofs of known results to identify and point to possiblesolutions for open problems in edge coloring.

The book begins with an introduction to graph theory and theconcept of edge coloring. Subsequent chapters explore importanttopics such as:

Use of Tashkinov trees to obtain an asymptotic positive solutionto Goldberg′s conjecture

Application of Vizing fans to obtain both known and newresults

Kierstead paths as an alternative to Vizing fans

Classification problem of simple graphs

Generalized edge coloring in which a color may appear more thanonce at a vertex

This book also features first–time English translations of twogroundbreaking papers written by Vadim Vizing on an estimate of thechromatic class of a p–graph and the critical graphs within a givenchromatic class.

Written by leading experts who have reinvigorated research inthe field, Graph Edge Coloring is an excellent book formathematics, optimization, and computer science courses at thegraduate level. The book also serves as a valuable reference forresearchers interested in discrete mathematics, graph theory,operations research, theoretical computer science, andcombinatorial optimization.

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

6 Goldberg′s Conjecture 155

6.1 Density and Fractional Chromatic Index 155

6.2 Balanced Tashkinov Trees 160

6.3 Obstructions 162

6.4 Approximation Algorithms 183

6.5 Goldberg′s Conjecture for Small Graphs 185

6.6 Another Classification Problem for Graphs 186

6.7 Notes 193

7 Extreme Graphs 197

7.1 Shannon′s Bound and Ring Graphs 197

7.2 Vizing′s Bound and Extreme Graphs 201

7.3 Extreme Graphs and Elementary Graphs 203

7.4 Upper Bounds for ÷′ Depending onÄ and ì 205

7.5 Notes 209

8 Generalized Edge Colorings of Graphs 213

8.1 Equitable and Balanced Edge Colorings 213

8.2 Full Edge Colorings and the Cover Index 222

8.3 Edge Colorings of Weighted Graphs 224

8.4 The Fan Equation for the Chromatic IndexX′f  228

8.5 Decomposing Graphs into Simple Graphs 239

8.6 Notes 243

9 Twenty Pretty Edge Coloring Conjectures 245

Appendix A: Vizing′s Two Fundamental Papers 269

A. 1 On an Estimate of the Chromatic Class of a p–Graph 269

References 272

A.2 Critical Graphs with a Given Chromatic Class 273

References 278

Appendix B: Fractional Edge Colorings 281

B. 1 The Fractional Chromatic Index 281

B.2 The Matching Polytope 284

B.3 A Formula for X′f  290

References 295

Symbol Index 312

Name Index 314

Subject Index 318

Michael Stiebitz, PhD, is Professor of Mathematics at theTechnical University of Ilmenau, Germany. He is the author ofnumerous journal articles in his areas of research interest, whichinclude graph theory, combinatorics, cryptology, and linearalgebra.

Diego Scheide, PhD, is a Postdoctoral Researcher in theDepartment of Mathematics at Simon Fraser University, Canada.

Bjarne Toft, PhD, is Associate Professor in theDepartment of Mathematics and Computer Science at the University ofSouthern Denmark.

Lene M. Favrholdt, PhD, is Associate Professor in theDepartment of Mathematics and Computer Science at the University ofSouthern Denmark.

College mathematics collections need just this sort ofrarity–accounts of major unsolved problems, elementary but stillcomprehensive.  Summing Up: Recommended.  Upper–divisionundergraduates.   (Choice, 1 September 2012)