Graph edge coloring : Vizing's theorem and Goldberg's conjecture
 Language
 English.
 Imprint
 Hoboken, N.J. : Wiley, c2012.
 Physical description
 xiv, 321 p. : ill ; 24 cm.
 Series
 Wiley series in discrete mathematics and optimization.
Access
Available online

Stacks

Unknown
QA166.247 .G73 2012

Unknown
QA166.247 .G73 2012
More options
Contributors
 Contributor
 Stiebitz, Michael, 1954
Contents/Summary
 Bibliography
 Includes bibliographical references (p. 295311) and indexes.
 Contents

 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 A and i 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 Index X'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 pGraph 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.
 (source: Nielsen Book Data)
 Publisher's 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 historical 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 graduatelevel course book for students of mathematics, optimization, and computer science.
(source: Nielsen Book Data)
Subjects
 Subject
 Graph coloring.
 Graph theory.
Bibliographic information
 Publication date
 2012
 Responsibility
 Michael Stiebitz ... [et al.].
 Series
 Wiley series in discrete mathematics and optimization
 Note
 "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 graduatelevel course book for students of mathematics, optimization, and computer science" Provided by publisher.
 ISBN
 9781118091371
 111809137X