Graph Coloring ProblemsJohn Wiley & Sons, 24 oct. 2011 - 320 pages Contains a wealth of information previously scattered in research journals, conference proceedings and technical reports. Identifies more than 200 unsolved problems. Every problem is stated in a self-contained, extremely accessible format, followed by comments on its history, related results and literature. The book will stimulate research and help avoid efforts on solving already settled problems. Each chapter concludes with a comprehensive list of references which will lead readers to original sources, important contributions and other surveys. |
Table des matières
1 Introduction to Graph Coloring | 1 |
2 Planar Graphs | 31 |
3 Graphs on Higher Surfaces | 59 |
4 Degrees | 77 |
5 Critical Graphs | 97 |
6 The Conjectures of Hadwiger and Hajós | 109 |
7 Sparse Graphs | 122 |
8 Perfect Graphs | 131 |
11 Constructions | 180 |
12 Edge Colorings | 190 |
13 Orientations and Flows | 209 |
14 Chromatic Polynomials | 220 |
15 Hypergraphs | 231 |
16 Infinite Chromatic Graphs | 251 |
17 Miscellaneous Problems | 261 |
277 | |
Autres éditions - Tout afficher
Expressions et termes fréquents
3-colorable 3-regular acyclic affirmative answer Albertson Amer answer is affirmative Berge bipartite graph Bollobas Borodin O.V. Chapter chromatic number chromatic polynomial chromatically unique Chvatal col(G coloring number coloring problem Combin Combinatorial complete graph complete subgraph Computing critical graphs cycle of length defined denote Discrete Math Discrete Mathematics disjoint edge-coloring editors embedded Erdbs Erdds exists finite first fixed four-color theorem G contains Gallai graph coloring graph G Graph Theory Graphen Griinbaum Gyarfas Hajnal Hajos hypergraph implies induced subgraph infinite integer Janos Bolyai k-chromatic graph k-critical Klein bottle Kostochka length at least Let G Lovasz maximum degree multigraph North-Holland NP-complete number of edges obtained odd cycle partition perfect graph conjecture personal communication Petersen graph planar graph polynomial algorithm Proc proof proved R.J. Wilson result Ringel satisfies Seymour Stiebitz strong perfect graph subgraph of G sufficient Thomassen Toft triangle-free graphs Tutte upper bound vertex set vertices of G Vizing