The theory of graph coloring has existed for more than 150 years. Historically, graph coloring involved finding the minimum number of colors to be assigned to the vertices so that adjacent vertices would have different colors. From this modest beginning, the theory has become central in discrete mathematics with many contemporary generalizations and applications. Generalization of graph coloring-type problems to mixed hypergraphs brings many new dimensions to the theory of colorings. A main feature of this book is that in the case of hypergraphs, there exist problems on both the minimum and the maximum number of colors. This feature pervades the theory, methods, algorithms, and applications of mixed hypergraph coloring. The book has broad appeal. It will be of interest to both pure and applied mathematicians, particularly those in the areas of discrete mathematics, combinatorial optimization, operations research, computer science, software engineering, molecular biology, and related businesses and industries. It also makes a nice supplementary text for courses in graph theory and discrete mathematics. This is especially useful for students in combinatorics and optimization. Since the area is new, students will have the chance at this stage to obtain results that may become classic in the future.
Author(s): Vitaly I. Voloshin
Series: FIM017
Publisher: American Mathematical Society, Fields Institute
Year: 2002
Language: English
Pages: 198
Front cover......Page 1
Title page......Page 3
Copyright page......Page 4
Dedication......Page 5
Epigraph......Page 7
Contents......Page 9
Preface......Page 13
0.1. Overview of graph coloring......Page 15
0.3. Unforeseen features of mixed hypergraph coloring......Page 17
0.4. Philosophical motivation of mixed hypergraph coloring......Page 18
0.5. Organization......Page 19
0.6. Acknowledgments......Page 23
1.1. General concepts......Page 25
1.2. A brief history of coloring theory......Page 30
1.3. Basic results on hypergraph coloring......Page 33
1.4. Hypertrees and chordal conformal hypergraphs......Page 37
2.1. Basic definitions......Page 41
2.2. Splitting-contraction algorithm......Page 44
2.3. Basic properties of the upper chromatic number......Page 48
2.4. Greedy $\mathcal{C}$-hypergraph coloring algorithms......Page 51
2.5. Algorithmic complexity......Page 56
2.6. Open problems......Page 57
3.1. Minimal uncolorable mixed hypergraphs......Page 59
3.2. Uncolorability measures and a greedy algorithm......Page 62
3.3. Colorability as an integer programming problem......Page 66
3.4. Special types of uncolorable mixed hypergraphs......Page 68
3.5. Open problems......Page 71
4.1. Preliminary......Page 73
4.2. Embeddings into uc mixed hypergraphs......Page 74
4.3. Separation using uc subhypergraphs......Page 75
4.4. Recursive operations......Page 77
4.6. UC mixed hypergraphs with $\chi\geq n—2$......Page 81
4.7. Uniquely colorable mixed hypertrees......Page 85
4.8. Open problems......Page 90
5.1. Basic concepts......Page 93
5.2. Minimal non-$\mathcal{C}$-perfect mixed hypergraphs......Page 95
5.3. $\mathcal{C}$-perfection of mixed hypertrees......Page 98
5.4. Algorithmic aspects of $\mathcal{C}$-perfection......Page 99
5.5. Open problems......Page 100
6.1. The smallest mixed hypergraphs with gaps......Page 103
6.2. Feasible sets and a doubling-shifting algorithm......Page 105
6.3. Smaller realization......Page 107
6.4. 0-1 realization......Page 109
6.5. Uniform bihypergraphs may have gaps......Page 110
6.6. Separation on uc preserves continuity......Page 112
6.7. Open problems......Page 113
7.1. Colorings......Page 115
7.2. Linear time algorithm for the upper chromatic number......Page 118
7.3. Chromatic spectrum is continuous......Page 119
7.4. Open problems......Page 120
8.1. Preliminaries......Page 121
8.2. Chromatic polynomial......Page 123
8.3. Consequences and examples......Page 125
8.4. A universal formula for chordal graphs......Page 129
8.5. Open problems......Page 131
9.1. Preliminaries......Page 133
9.2. Unique colorability, $n$ even......Page 135
9.3. Unique colorability, $n$ odd......Page 137
9.5. Upper chromatic number......Page 139
9.6. Open problems......Page 141
10.1. Classic planar hypergraphs......Page 143
10.2. Coloring bitriangulations......Page 144
10.3. Bounds for the upper chromatic number......Page 149
10.4. Gaps in the chromatic spectrum......Page 151
10.5. Open problems......Page 152
11.1. Steiner systems......Page 155
11.2. Steiner triple systems......Page 157
11.3. Steiner quadruple systems......Page 163
11.4. Open problems......Page 167
12.1. List colorings without lists......Page 169
12.2. Ramsey, anti-Ramsey and related problems......Page 170
12.3. Mixed hypergraphs and integer programming......Page 172
12.4. Resource allocation......Page 176
12.7. Database management......Page 179
12.8. Molecular biology......Page 180
12.9. Genetics of populations......Page 182
12.10. Natural number interpretation......Page 183
Bibliography......Page 185
List of Figures......Page 193
Index......Page 195
Titles in This Series......Page 197
Back cover......Page 198
