Graph Edge Coloring
Vizing's Theorem and Goldberg's Conjecture
By Michael Stiebitz, Diego Scheide, Bjarne Toft et al.
Graph Edge Coloring
Vizing's Theorem and Goldberg's Conjecture
By Michael Stiebitz, Diego Scheide, Bjarne Toft et al.
- Gebundenes Buch
- Merkliste
- Auf die Merkliste
- Bewerten Bewerten
- Teilen
- Produkt teilen
- Produkterinnerung
- Produkterinnerung
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…mehr
- Graph Partitioning184,99 €
- Frank HöppnerFuzzy Cluster Analysis248,99 €
- James L. JohnsonProbability and Statistics for Computer Science315,99 €
- Ingvar EidhammerProtein Bioinformatics105,99 €
- The Handbook of Information and Computer Ethics209,99 €
- Mohammed CherietCharacter Recognition Systems177,99 €
- Richard W. SelbySoftware Engineering142,99 €
-
-
-
- Produktdetails
- Reihe PoLYpeN
- Verlag: Wiley & Sons
- Artikelnr. des Verlages: 1W118091370
- 1. Auflage
- Seitenzahl: 344
- Erscheinungstermin: 14. Februar 2012
- Englisch
- Abmessung: 241mm x 164mm x 25mm
- Gewicht: 622g
- ISBN-13: 9781118091371
- ISBN-10: 111809137X
- Artikelnr.: 34447610
- Reihe PoLYpeN
- Verlag: Wiley & Sons
- Artikelnr. des Verlages: 1W118091370
- 1. Auflage
- Seitenzahl: 344
- Erscheinungstermin: 14. Februar 2012
- Englisch
- Abmessung: 241mm x 164mm x 25mm
- Gewicht: 622g
- ISBN-13: 9781118091371
- ISBN-10: 111809137X
- Artikelnr.: 34447610
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 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 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
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 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 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