## Graph Coloring ProblemsContains 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

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 | |

### Other editions - View all

### Common terms and phrases

3-colorable 3-regular acyclic afﬁrmative answer Albertson Amer answer is afﬁrmative 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 deﬁned denote Discrete Math Discrete Mathematics disjoint edge-coloring editors embedded Erdbs Erdds exists ﬁnite ﬁrst ﬁxed four-color theorem G contains Gallai graph coloring graph G Graph Theory Graphen Griinbaum Gyarfas Hajnal Hajos hypergraph implies induced subgraph inﬁnite 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 satisﬁes Seymour Stiebitz strong perfect graph subgraph of G sufﬁcient Thomassen Toft triangle-free graphs Tutte upper bound vertex set vertices of G Vizing