Graph Edge Coloring

Vizing's Theorem and Goldberg's Conjecture

Inbunden, Engelska, 2012

1 352 kr

Beställningsvara. Skickas inom 5-8 vardagar. Fri frakt över 249 kr.

Beskrivning

Features recent advances and new applications in graph edge coloring Reviewing recent advances in the Edge Coloring Problem, Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture provides an overview of the current state of the science, explaining the interconnections among the results obtained from important graph theory studies. The authors introduce many new improved proofs of known results to identify and point to possible solutions for open problems in edge coloring.The book begins with an introduction to graph theory and the concept of edge coloring. Subsequent chapters explore important topics such as: Use of Tashkinov trees to obtain an asymptotic positive solution to Goldberg's conjecture Application of Vizing fans to obtain both known and new results Kierstead paths as an alternative to Vizing fans Classification problem of simple graphs Generalized edge coloring in which a color may appear more than once at a vertex This book also features first-time English translations of two groundbreaking papers written by Vadim Vizing on an estimate of the chromatic class of a p-graph and the critical graphs within a given chromatic class.Written by leading experts who have reinvigorated research in the field, Graph Edge Coloring is an excellent book for mathematics, optimization, and computer science courses at the graduate level. The book also serves as a valuable reference for researchers interested in discrete mathematics, graph theory, operations research, theoretical computer science, and combinatorial optimization.

Produktinformation

Utgivningsdatum:2012-03-02
Mått:163 x 236 x 25 mm
Vikt:635 g
Format:Inbunden
Språk:Engelska
Antal sidor:344
Förlag:John Wiley & Sons Inc
ISBN:9781118091371

Utforska kategorier

Mer om författaren

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. Diego Scheide, PhD, is a Postdoctoral Researcher in the Department of Mathematics at Simon Fraser University, Canada.Bjarne Toft, PhD, is Associate Professor in the Department of Mathematics and Computer Science at the University of Southern Denmark.Lene M. Favrholdt, PhD, is Associate Professor in the Department of Mathematics and Computer Science at the University of Southern Denmark.

Recensioner i media

“College mathematics collections need just this sort of rarity-accounts of major unsolved problems, elementary but still comprehensive. Summing Up: Recommended. Upper-division undergraduates.” (Choice, 1 September 2012)

Innehållsförteckning

Preface xi 1 Introduction 11.1 Graphs 11.2 Coloring Preliminaries 21.3 Critical Graphs 51.4 Lower Bounds and Elementary Graphs 61.5 Upper Bounds and Coloring Algorithms 111.6 Notes 152 Vizing Fans 192.1 The Fan Equation and the Classical Bounds 192.2 Adjacency Lemmas 242.3 The Second Fan Equation 262.4 The Double Fan 312.5 The Fan Number 322.6 Notes 393 Kierstead Paths 433.1 Kierstead's Method 433.2 Short Kierstead's Paths 463.3 Notes 494 Simple Graphs and Line Graphs 514.1 Class One and Class Two Graphs 514.2 Graphs whose Core has Maximum Degree Two 544.3 Simple Overfull Graphs 634.4 Adjacency Lemmas for Critical Class Two Graphs 734.5 Average Degree of Critical Class Two Graphs 844.6 Independent Vertices in Critical Class Two Graphs 894.7 Constructions of Critical Class Two Graphs 934.8 Hadwiger's Conjecture for Line Graphs 1014.9 Simple Graphs on Surfaces 1054.10 Notes 1105 Tashkinov Trees 1155.1 Tashkinov's Method 1155.2 Extended Tashkinov Trees 1275.3 Asymptotic Bounds 1395.4 Tashkinov's Coloring Algorithm 1445.5 Polynomial Time Algorithms 1485.6 Notes 1526 Goldberg's Conjecture 1556.1 Density and Fractional Chromatic Index 1556.2 Balanced Tashkinov Trees 1606.3 Obstructions 1626.4 Approximation Algorithms 1836.5 Goldberg's Conjecture for Small Graphs 1856.6 Another Classification Problem for Graphs 1866.7 Notes 1937 Extreme Graphs 1977.1 Shannon's Bound and Ring Graphs 1977.2 Vizing's Bound and Extreme Graphs 2017.3 Extreme Graphs and Elementary Graphs 2037.4 Upper Bounds for ÷' Depending on Ä and ì 2057.5 Notes 2098 Generalized Edge Colorings of Graphs 2138.1 Equitable and Balanced Edge Colorings 2138.2 Full Edge Colorings and the Cover Index 2228.3 Edge Colorings of Weighted Graphs 2248.4 The Fan Equation for the Chromatic Index X'f 2288.5 Decomposing Graphs into Simple Graphs 2398.6 Notes 2439 Twenty Pretty Edge Coloring Conjectures 245Appendix A: Vizing's Two Fundamental Papers 269A. 1 On an Estimate of the Chromatic Class of a p-Graph 269References 272A.2 Critical Graphs with a Given Chromatic Class 273References 278Appendix B: Fractional Edge Colorings 281B. 1 The Fractional Chromatic Index 281B.2 The Matching Polytope 284B.3 A Formula for X'f 290References 295Symbol Index 312Name Index 314Subject Index 318